再学二分查找

三种二分查找代表各自的意义

①区间是左闭右闭,依靠mid来查找目标

	// 区间是闭区间[left,right]
	public int search(int[] nums, int target) {
		int left = 0;
		int right = nums.length - 1;
		while (left <= right) { //重点
			int mid = left + (right - left) / 2;
			if (nums[mid] == target) return mid;
			if (nums[mid] < target) {
				left = mid + 1;
			} else {
				right = mid - 1;//重点
			}
		}
		return -1;
	}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

②区间是左闭右开,依靠mid来查找目标，right下标必然会大于mid

    // 区间是左闭右开[left,right)
	public int search(int[] nums, int target) {
		int left = 0;
		int right = nums.length;
		while (left < right) {
			int mid = left + (right - left) / 2;
			if (nums[mid] == target) return mid;
			if (nums[mid] < target) {
				left = mid + 1;
			} else {
				right = mid;
			}
		}
		return -1;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

③区间是左闭右开,不依靠mid,当二分到区间就有一个值时,该值只有两种结果,是目标返回left,或者不是目标返回-1,

    //不通过mid查找元素,但是要保证区间长度大于1,
    //即必须保证最后一次循环即只有两个元素时不会出现问题
    //左闭右开时,mid靠右
    //什么是mid靠右,就是只有两个元素时指向右边元素.假设两个元素为(1,5),下标mid=1=0+(2-0)/2,
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length;
        while(left + 1 < right){
            int mid = left + (right-left)/2;//mid靠右
            if(target >= nums[mid]){
             //①是因为nums[mid]可能=target,所以不能mid+1;
            //②又因为只有两个元素时mid靠右,即mid比left大,因此left往前移了一步.不会导致死循环
                left = mid ; 
            }else{
           		right = mid ;//right满足不在当前区间	
            }  
        }
        if(nums[left]==target) return left;
        else return -1;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

④区间是左闭右闭,不依靠mid,当二分到区间就有一个值时,该值只有两种结果,是目标返回right,或者不是目标返回-1,

    //不通过mid查找元素,但是要保证区间长度大于1,即必须保证退出循环的时候区间长度=1
   public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length-1;
        while(left < right){
            int mid = left + (right-left)/2;//mid靠左,因为靠左,所以后面也需要变化
            //1.因为天生靠左,所以在只有两个元素时,必须要将target=nums[mid]放在target<=nums[mid]上,这样right指向元素才有可能=target,这样才能避免死循环
            if( target <= nums[mid]){
                right = mid ;//确保在target=nums[mid]不后退;在target
            }else{
             	left = mid+1 ;//确保left进了一步
            }  
        }
        if(nums[right]==target) return right;
        else return -1;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

总结上面四种方式,①②比较好理解,只要能理解right是否在当前区间就能把边界值搞定。
③④之所以要考虑mid靠左靠右和考虑<=还是>=是因为需要解决死循环的问题,因为left或者right=mid,有可能会导致死循环,但是如果mid靠左,target<=nums[mid],或者mid靠右,target>=nums[mid]就可以避免死循环.