题目(easy)：
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
注：左闭右开，左闭右闭，两种区间规则写出来的二分法不一致
思路
题目的前提是数组为有序数组，且数组中无重复元素。
对区间的定义得想清楚，区间的定义就是不变量，要满足循环不变量规则。
第一种写法：左闭右闭，即 [left, right]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| const search = (nums, target) => {
let mid;
let left = 0;
let right = nums.length - 1;
while(left <= right) {
mid = left + ((right - left) >> 1);
if (nums[mid] > target) {
right = mid - 1;
} else if (nums[mid] < target) {
left = mid + 1;
} else {
return mid;
}
}
return -1;
};
|
时间复杂度：O(logn)。
空间复杂度：O(1)。
第二种写法：左闭右开，即 [left, right)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| const search = (nums, target) => {
let mid;
let left = 0;
let right = nums.length;
while(left < right) {
mid = left + ((right - left) >> 1);
if (nums[mid] > target) {
right = mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else {
return mid;
}
}
return -1;
};
|
