营销型外贸网站制作,用地方别名做网站名,好网,建设网站手机版题目链接
题目描述 给定一个排序数组和一个目标值#xff0c;在数组中找到目标值#xff0c;并返回其索引。如果目标值不存在于数组中#xff0c;返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 示例 1: 输入: nums [1,3,5,6], target 5
输出…题目链接
题目描述 给定一个排序数组和一个目标值在数组中找到目标值并返回其索引。如果目标值不存在于数组中返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 示例 1: 输入: nums [1,3,5,6], target 5
输出: 2示例 2: 输入: nums [1,3,5,6], target 2
输出: 1示例 3: 输入: nums [1,3,5,6], target 7
输出: 4提示: 1 nums.length 104-104 nums[i] 104nums 为 无重复元素 的 升序 排列数组-104 target 104 分析思路 前提有序数组数组中无重复元素一旦有重复元素使用二分查找法返回的元素下标可能不是唯一的确认方法二分查找法注二分法中关于区间的定义一般为两种——“左闭右闭[left, right]” 或 “左闭右开[left, right)” 代码实现
实现一左闭右闭
class Solution {
public:int searchInsert(vectorint nums, int target) {int left 0;int right nums.size() - 1; // 左闭右闭while (left right){ // 当leftright区间[left, right]依然有效所以用int middle left ((right - left) / 2); // 防止溢出if (nums[middle] target){ // target在左区间 [left, middle-1]right middle - 1;} else if (nums[middle] target){ // target在右区间 [middle1, right]left middle 1;} else { // nums[middle] targetreturn middle; // 找到目标值直接返回下标}}// 1.目标值在数组所有元素之前 [0, -1]// 2.目标值插入数组中的位置 [left, right]// 3.目标值在数组所有元素之后 [nums.size(), nums.size()-1]return right 1;// return left;}
};
实现二左闭右开
class Solution {
public:int searchInsert(vectorint nums, int target) {int left 0;int right nums.size(); // 左闭右开while (left right){ // 当leftright区间[left, right)无效int middle left ((right - left) / 2); // 防止溢出// int middle left ((right - left) 1); // 按位右移运算符等同于变量除以2if (nums[middle] target){ // target在左区间 [left, middle)right middle;} else if (nums[middle] target){ // target在右区间 [middle1, right)left middle 1;} else { // nums[middle] targetreturn middle; // 找到目标值直接返回下标}}// 1.目标值在数组所有元素之前 [0, 0)// 2.目标值插入数组中的位置 [left, right)// 3.目标值在数组所有元素之后 [nums.size(), nums.size() )return right;// return left;}
};
参考来源代码随想录
补充位移运算符为何能将数据乘以或除以 ?
按位右移运算符将变量除以按位左移运算符将变量乘以。
例如
变量num的值为16其二进制表示为10000。将num右移1位结果为01000即8这相当于将其减半将num右移两位变成了00100即4相当于计算num的1/4。向左移1位时结果为100000即32向左移两位的结果为1000000即64相当于计算num的2倍和4倍。
