leetcode链接：
https://leetcode.cn/problems/binary-search/description/
方案一
思考过程，存在纰漏，只有一个数据，并且恰好是target的时候无法正常返回，只能多添加一个判断语句
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| int result = -1;
int left = 0, right = nums.length - 1;
if (nums[0] == target) {
return 0;
}
while (left < right) {
if (nums[((left + right) /2 + 1)] > target) {
right = (left + right) /2;
} else if (nums[((left + right) /2 + 1)] == target) {
return (left + right) /2 + 1;
} else {
left = (left + right) /2 + 1;
}
}
return result;
|
代码随想录
https://programmercarl.com/0704.%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE.html
难点：
对区间的定义的理解，在循环中如何根据查找区间的定义来做边界处理。
（版本一）左闭右闭区间
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public int search(int[] nums, int target) {
if (target < nums[0] || target > nums[nums.length - 1]) {
return -1;
}
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + ((right - left) >> 1);
if (nums[mid] == target)
return mid;
else if (nums[mid] < target)
left = mid + 1;
else if (nums[mid] > target)
right = mid - 1;
}
return -1;
}
}
|
（版本二）左闭右开区间
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public int search(int[] nums, int target) {
int left = 0, right = nums.length;
while (left < right) {
int mid = left + ((right - left) >> 1);
if (nums[mid] == target)
return mid;
else if (nums[mid] < target)
left = mid + 1;
else if (nums[mid] > target)
right = mid;
}
return -1;
}
}
|