一、二分查找
1.二分查找方法概述
- 二分查找是针对有序数组的一种查找方式。是利用（letf+right）/2 = mid的方式来对半缩短搜索范围的一种方法，一次查找，搜索的范围就会减半。相较于简单查找找寻一个target需要n步，则二分查找则最多只需查找log2n步。
2.具体实现
方法一
点击查看代码
class Solution {
public int search(int[] nums, int target) {
int left = 0;
int right = nums.length -1;
while(left <= right){
int mid = (right+left)/2;
if(nums[mid] == target){
return mid;
}else if(nums[mid] > target){
right = mid - 1;
}else{
left = mid + 1;
}
}
return -1;
}
}
方法二
点击查看代码
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;
}
}
3.要点总结
1.关于length是否-1的问题
- length是否-1取决于区间是左闭右闭区间（ [ ] ），还是左闭右开区间( [ ) ).当选取左闭右闭区间（ [ ] ）时，length则需要-1，因为搜索区间包含右边界值，即整个数组下标都能取到则length需要-1。如果是左闭右开区间( [ ) )，length则不需要-1，因为右边界值不包含在搜索区间内，右边界值的取值无意义。
2.关于循环条件letf是<=还是<的问题
- 当区间是左闭右闭区间（ [ ] ），left则取<= right。当区间是左闭右开区间( [ ) )时，则不取= 。
3.关于赋值是赋mid的还是mid-1的问题
- 当区间是左闭右闭区间（ [ ] ）时，mid则需要-1，因为mid包含在有效值区间，已经排除。当区间是左闭右开区间( [ ) )时，mid则不需要-1，因为mid的值不包含在有效的搜索区间内，无需排除，所以无需-1。
仅供个人参考，同时欢迎批评指正。
标签：二分,right,int,mid,查找,左闭,left From： https://www.cnblogs.com/neverlate/p/17011463.html