二分查找

link：704. 二分查找 - 力扣（LeetCode）
image-20240923152617533

思路分析

题目给出数组升序 ，想到二分查找（好吧其实题目也给出来了w）
找到mid，根据逻辑大小缩小范围比较.

全包围[lefg,right]

假如数组大小为6，取值范围就是[0,5].闭区间使得定义left = 0，right = nums.length-1（防止越界指针无效，也是根据此处可以反推没有左开右闭情况）
left指针是0.right是5，这个时候left == right是有效的，结束条件也就是left<=right，再根据mid位置进行判断，target是再mid左边还是右边或者是幸运的查找到目标位置.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int search(int[] nums, int target) {
       
        //看到数组习惯性反应越界问题
        //闭区间
       
        int right = nums.length - 1;
        int left = 0;
        while(left <= right) {
            int mid = left + (right - left) / 2;
            if(nums[mid] < target) {
                left = mid + 1;
            }else if(nums[mid] > target) {
                right = mid -1;
            }else {
                return mid;
            }
        }
        return -1;
    }
}
左闭右开[left,rigjht)

同样的条件但是right指针指向nums.length，对应的left == right没有意义.所以判断条件是left < right.如果target在nums[mid]左边的话，把left赋值为mid+1，但是反过来target在nums[mid]右边的话，就要赋值left为mid【右边开mid指的指针不参加下一次循环判读】

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int search(int[] nums, int target) { 
        int right = nums.length;
        int left = 0;
        while(left < right) {
            int mid = left + (right - left) / 2;
            if(nums[mid] < target) {
                left = mid + 1;
            }else if(nums[mid] > target) {
                right = mid;
            }else {
                return mid;
            }
        }
        return -1;
    }
}
全开(left,right)

分析同上述 只不过全开两种情况都赋值为mid.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int search(int[] nums, int target) { 
        int right = nums.length;
        int left = -1;
        while(left + 1 < right) {
            int mid = left + (right - left) / 2;
            if(nums[mid] < target) {
                left = mid;
            }else if(nums[mid] > target) {
                right = mid;
            }else {
                return mid;
            }
        }
        return -1;
  }
}
Tips

1.区间问题，判断条件是否能遍历所有下标.
2.其实将mid取值方法改成left+((right-left)>>1)【和 / 2一样】是最好的，直接用（left+right）/ 2和（left+right）// 2 【向下取整】 只适用于少数据全包围情况，此情况left和right都是int范围，取值范围是-2147483648-2147483647，当两个数值很接近边界值的时候相加很容易出现负值
3.（right-left ）/ 2 只是表示了left和right指针之间距离的一半，不能表示mid所在的位置，用left加上距离的一半刚好能进行表示.