二分查找

Posted on

左闭右开，缩小边界时，左边需要加1，右边不需要。

1
2
3
4
5
6
7
8
public int search(int[] a,int start,int end,int target){/ /前闭后开，
    while(start<end){
        int mid=start+(end-start)/2;
        if(a[mid]<target)start=mid+1;
        else
            end=mid;
    }
    return start;

升序的旋转，{1，2，3，4，5}旋转为 {3，4，5，1，2}，在查找某个数时，如果数组中没有重复的数字，把数组从中间分为两个部分。

  • left<right，说明没有旋转；
    • 如果mid大于left的，说明左边是有序的；
    • mid小于left，说明右边数组是有序的。
  • 有重复数字的情况：如果left=mid=right，那么无法判断，只能顺序遍历。
  • 左边大于等于不能同时一起判断，=只能和<在一块，即left<=mid。右边反过来。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public int findMin(int[] nums) {
    int length=nums.length;
    int left=0;
    int right=length-1;
    int mid=left;
    while(nums[left]>=nums[right]){
        if(right-left==1){
            mid=right;
            break;
        }
        mid=(left+right)/2;
        if(nums[left]<=nums[mid]){
            if(nums[left]==nums[mid]&&nums[left]==nums[right]){
                return find(nums,left,right);
            }else{
                left=mid;
            }
        }else{
            right=mid;
        }
    }
    return nums[mid];
}
public int find(int[] nums,int left,int right){
    int min=nums[left];
    for(int i=left+1;i<=right;i++){
        if(nums[i]<min){
            min=nums[i];
        }
    }
    return min;
}