阿聪的小破站algo›frame
二分查找算法详解
我们都知道二分查找的大致思路，就是定义一个左指针和一个右指针，去这两个指针的中间值，判断是否和目标值一样，如果一样就返回当前下标；如果不等于，就判断中间值与目标值的大小，如果中间值小于目标值，那么左指针就走到中间值下标+1的位置；如果中间值大于目标值，那么右指针就走到中间值下标-1的位置，以此类推。
class Solution {
public int search(int[] nums, int target) {
int left = 0, right = nums.length-1;
while(left<=right){
int index = left + (right-left)/2; //
int val = nums[index];
if(val == target){
return index;
}
else if(val<target){
left = index+1;
}
else{
right = index-1;
}
}
return -1;
}
}这里有两个问题需要思考
1、while当中是<=为什么不是<?
小于等于表示搜索区间两侧都能取到，比如[left, right]，如果只是小于的话，搜索区间就表示[left, right)， 右边就取不到了。
2、为什么是left = index+1?
因为我们使用的是两边毕区间的搜索区间，所有当发现index的位置不是我们的目标值的时候，就会从index-1或者index+1的范围再来计算