推荐看力扣上这篇的讲解,更加详细,我这里只讲解左闭右闭的情况

力扣https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/solutions/13230/er-fen-cha-zhao-suan-fa-xi-jie-xiang-jie-by-labula/

大前提:二分查找要求查找的数组必须是有序的

0.最普通的二分查找

这种二分查找主要针对查找的值是否存在,并且含有重复元素(即要求查找值)的时候不要求查找到此重复元素的具体位置:如该重复元素最左边或最右边

例如:[5,7,7,8,8,10],要求查找7这个元素,最终查找的index为2,但是无法处理查找index=1的7元素

  public static int binarySearch3(int[] arr, int value) {
        int left = 0;
        int right = arr.length - 1;
        int mid;
        while (left <= right) {
            mid = (left + right) / 2;
            if (arr[mid] > value) {//向左找
                right = mid - 1;
            } else if (arr[mid] < value) {//向右找
                left = mid + 1;
            } else {
                return mid;
            }
 
        }
        return -1;
 
 
    }

1.二分查找

存在重复值的二分查找

针对数组排好序,并且数组中含有重复元素,如[5,7,7,8,8,10]

力扣针对这两个问题:力扣

1.查找第一个为7的元素的下标(左边界)

此时返回值可能存在四种情况:

例如:

• [5,7,7,8,8,10],最后数组中含有7这个元素,所以最终查找到最左边7,返回下标:1
• [5,6,6,8,8,10],数组中不存在7这个元素,此时返回第一个大于7的元素的下标,即元素8第一个元素下标:3
• [1,2,3,4,5],数组中也不包含7,并且所有元素小于7,此时left会返回nums.length,即下标:5,这个时候不能nums[left]判断,因为指标越界
• [8,9,10,11,12],数组中也不包含7,并且所有元素大于7,此时循环的过程中,left的值一直保持0,直到最后right<left,最终下标返回:0

第一种:判断是否最终查找到最左边的最终值

 //寻找左边界
    public int binarySearchLeft(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        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 {
                right = mid - 1;
            }
        }
        if (left == nums.length)
            return -1;
        return nums[left] == target ? left : -1;
    }

第二种:不判断    (更加常用,可以到具体调用完方法之后再根据题意做具体的判断)

    public int left_BinarySerach(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] >= target) {
                right = mid - 1;

            } else if (nums[mid] < target) {
                left = mid + 1;

            }
        }
        return left;
    }

2.查找最后一个为7的元素的下标(右边界)

此时返回值可能存在四种情况:

例如

• [5,7,7,8,8,10],最后数组中含有7这个元素,所以最终查找到最右边7,返回下标:2
• [5,6,6,8,8,10],数组中不存在7这个元素,此时返回最后一个小于7的元素的下标,即6最后一个元素下标:2
• [1,2,3,4,5],数组中也不包含7,并且所有元素小于7,此时此时循环的过程中,right的值一直保持nums.length-1(即4),直到最后right<left,最终下标返回:4
• [8,9,10,11,12],数组中也不包含7,并且所有元素大于7,right会返回下标为-1这个时候不能nums[right]判断,因为指标越界

第一种:判断是否最终查找到最右边的最终值

  //寻找右边界
    public int binarySearchRight(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        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 {
                left = mid + 1;
            }
        }
        if (right == -1)
            return -1;
        return nums[right] == target ? right : -1;
    }

第二种:不判断

    public int right_BinarySerach(int[] nums, int num) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] > num) {
                right = mid - 1;

            } else if (nums[mid] <= num) {
                left = mid + 1;

            }
        }
        return right;
    }

3.x的平方根

力扣:力扣

直接代码实现

  public int mySqrt(int x) {
        int l = 0, r = x, ans = -1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if ((long) mid * mid <= x) {
                ans = mid;
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return ans;
    }