image.png

思路

• 二分查找的原理从排好序的数组中,将数组从中间索引处一份为二, 拆分成左右两个子数组进行搜索, 左右两个子数组分别在根据自身中间索引在一份二位, 一直到left和right两个索引相遇时循环结束

先初始化left = 0, 从数组的最左边开始,right = nums.length - 1 从数组的最右边开始
中间索引mid = left + (right - left)/2; 这样是为了防止超大的int值越界
while (left ? right) 循环的条件是left < right 还是left <= right呢, 这其实是根据我们定义的区间是[左闭右闭],还是[左闭右开)来决定
如果是左闭右闭就是 <= , 因为[left, rigt] [1,1] 区间既包含左也包含右, 所以left <= right 1<=1 是合理的
如果是 left < right 假设区间是[1,1] ,那么 left = 1, right = 1, 在这个区间不合理
left < right 的情况是适用于[left, right), [1,1)左闭右开 指的是不包含右区间的数 , 如果left = right 在这个区间里没有意义, 所以left < right
那么在[左闭右开]的情况中, nums[mid] > target 时, 说明target在数组的左边, 我们应该更新左区间的右边界, 因为nums[mid] 肯定不符合左区间的边界,所以right = mid - 1 等于mid的前一个
如果nums[mid] < target 时, 说明target在数组的右边, 应该更新右区间的左边界,nums[mid] < target, mid 肯定不符合右区间的边界, 所以left = mid + 1;
相等直接返回mid
找不到直接返回-1

    // 左闭右闭区间解法, 包含最右边的值
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        int mid = left + (right - left) / 2;
        while (left <= right) {
            if (nums[mid] > target) {
                right = mid - 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                return mid;
            }
        }
        return -1;
    }

    // 左闭右开解法, 不包含最右边的值
    // [left, right) [1,1)
    public int search1(int[] nums, int target) {
        int left = 0;
        int right = nums.length;
        while (left < right) {
            int mid = left + ((right - left) >>1);
            if (nums[mid] > target) {
                right = mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                return mid;
            }
        }
        return -1;
    }

leetcode