二分查找及查找左、右边界

矫情吗；* 2024-04-06 12:48 10阅读 0赞

**目录**

二分查找

概念：

详细举例：

那么问题来了

实现代码：

查找左右边界：

概念：

举例：

编写思路：

实现代码：

--------------------

## 二分查找 ##

### 概念： ###

通过将一组“有序”的‘组’不断的一分为二的方法，快速在这个‘组’中找到想要查找的数

### 详细举例： ###

在‘组’【0,1,2,3,4,5,6,7,8】中，想要快速的找到8的位置。接下来就用二分查找法进行查找。

在0-8位置的查找范围中，找到中间位置的元素，与查找元素8进行比较。

得到中间元素4小于查找元素8

所以根据‘序’，知道查找元素8在查找范围0-8中的右半部分

所以可以缩小查找范围，知道新范围在4右边的位置5，到8是我们新的查找范围

在新范围5-8中，找到中间位置的元素，与查找元素8进行比较。

得到中间元素6小于查找元素8

所以根据‘序’，知道查找元素8在查找范围5-8中的右半部分

所以可以缩小查找范围，知道新范围在6右边的位置7，到8是我们新的查找范围

在新范围7-8中，找到中间位置的元素，与查找元素8进行比较。

得到中间元素7小于查找元素8

所以根据‘序’，知道查找元素8在查找范围7-8中的右半部分

所以可以缩小查找范围，知道新范围在7右边的位置8，到8是我们新的查找范围

在新范围8-8中，找到中间位置的元素，与查找元素8进行比较。

得到中间元素8等于查找元素8

所以返回8的位置，即8

至此，查找完毕

### 那么问题来了 ###

中间元素怎么找的？为什么5-8的中间元素是6呢？

计算方法为：（左范围+右范围）/2

所以，这就解释了为什么是6

这里需要注意，推荐使用“左范围+（右范围-左范围）/2”

这样可以避免加法运算可能导致的溢出问题

### 实现代码： ###

public static int binarySearch(int[] arr, int search) {
            int left = 0, mid, right = arr.length - 1;
    
            while (left <= right) {
                mid = left + (right - left) / 2;
                if (arr[mid] == search)
                    return mid;
                else if (arr[mid] < search) {
                    left = mid + 1;
                } else if (arr[mid] > search) {
                    right = mid - 1;
                }
            }
            return -1;
        }

## 查找左右边界： ##

### 概念： ###

查找此数在数组出现的为最左边的位置即查找左边界，右边界同理

### 举例： ###

我想要在arr=\[1,2,2,2,2,4,7,8,9,99\]中查找2，这个时候会看见好几个2，此时arr\[1\]是2在数组的左边出现的，所以arr\[1\]就是我要找的左边界。右边界同理。

### 编写思路： ###

通过二分查找的“缩范围”的思想，将范围尽量向左缩小，即遇到2的时候，我往左缩一下范围看看，看看此时找到的2的左侧的范围，还有没有2了，有就接着缩，没有就证明此时的是要找的左边界了，就可以输出这个位置了

### 实现代码： ###

public static int binarySearchLeft(int[] arr, int search) {
            int left = 0, mid, right = arr.length - 1;
    
            while (left <= right) {
                mid = left + (right - left) / 2;
                if (arr[mid] == search) {
                    right = mid - 1;
                } else if (arr[mid] < search) {
                    left = mid + 1;
                } else if (search < arr[mid]) {
                    right = mid - 1;
                }
            }
            if (left >= arr.length || arr[left] != search)
                return -1;
            return left;
        }

此时需要在后面加上if语句进行越界及未找到的判断，是则返回-1；反之返回对应下标。

查找右边界源码：

int binarySearchRight(int[] arr, int search) {
            int left = 0, right = arr.length - 1;
            while (left <= right) {
                int mid = left + (right - left) / 2;
                if (arr[mid] < search) {
                    left = mid + 1;
                } else if (arr[mid] > search) {
                    right = mid - 1;
                } else if (arr[mid] == search) {
                    left = mid + 1;
                }
            }
            if (right < 0 || arr[right] != search)
                return -1;
            return right;
        }

与查找左边界同理，此即向右边缩小查找范围

学习源于、超细致详解[：为了学会二分搜索，我作了首诗 - 知乎][-]，膜拜大佬.jpg

[-]: https://zhuanlan.zhihu.com/p/112078167