二分查找（精确查找、范围搜索）

1. 二分查找概述

        二分查找法，也称为二分搜索法或折半查找法，是一种在有序数组中查找特定元素的搜索算法。其基本思想是，通过不断将待查找的区间分成两半，并与待查找的元素进行比较，根据比较结果调整查找区间，直到找到元素或区间被缩小至0为止。时间复杂度为O(log n)

• 使用条件：二分查找要求数组必须是有序的，无论是升序还是降序。如果数组无序，则需要先进行排序操作。
• 易错点：while循环过程中，left与right的关系容易错乱；left与right指针的移动容易错。
• 查找情况：二分查找最常见的就是查找某一个序列中存在的精确值target，然而还有一部分是利用二分查找来进行范围划分。

2. 精确查找

        为了捋清楚终止条件与指针移动如何确定，需要先从搜索定义区间入手，搜索区间可以分为【left，right】和【left，right）。

2.1 【left，right】

当搜索区间为【left，right】时，说明二分查找过程中，每次搜索区间应该均需要满足该定义。此时二分查找步骤为：

1. 确定查找区间：设数组为arr，查找范围为[left, right]，初始时left=0，right=n-1，其中n为数组arr的长度。
2. 确定循环条件：由于区间是左闭右闭，所以left = right符合定义区间，因此搜索过程中应当满足的条件为while（left <= right）
3. 计算中间位置：mid = (left + right) / 2（注意，为了避免整数相加导致的整数溢出问题，有时也使用mid = left + (right - left) / 2的计算方式）。
4. 比较中间元素与目标值： 如果arr[mid]等于目标值，则查找成功，返回mid。如果arr[mid]大于目标值，则说明目标值在左半部分，且arr[mid]将不会再需要处于搜索区间内了（因为arr[mid]已经一定不等于target了），则将查找范围更新为[left, mid-1]，right = mid - 1。 如果arr[mid]小于目标值，则说明目标值在右半部分,且arr[mid]将不会再需要处于搜索区间内了（因为arr[mid]已经一定不等于target了），将查找范围更新为[mid+1, right]，left = mid + 1。
5. 重复步骤2和步骤3：直到找到目标值或查找范围为空（即left > right），如果查找范围为空，则说明目标值不存在于数组中。

public static int binarySearch(int[] arr, int target) {  
        int left = 0;  
        int right = arr.length - 1;  
  
        while (left <= right) {  
            int mid = left + (right - left) / 2; // 防止溢出，同时更准确地找到中间位置  
            if (arr[mid] == target) {  
                return mid; // 找到目标元素，返回索引  
            } else if (arr[mid] < target) {  
                left = mid + 1; // 目标元素在右半部分  
            } else {  
                right = mid - 1; // 目标元素在左半部分  
            }  
        }  
  
        // 未找到目标元素，返回-1  
        return -1;  
 }  
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

2. 2 【left，right）

当搜索区间为【left，right）时：

1. 确定查找区间：设数组为arr，查找范围为[left, right），初始时left=0，right=n，其中n为数组arr的长度。
2. 确定循环条件：由于区间是左闭右开，所以left != right符合定义区间，因此搜索过程中应当满足的条件为while（left < right）
3. 计算中间位置：mid = (left + right) / 2（注意，为了避免整数除法导致的精度问题，有时也使用mid = left + (right - left) / 2的计算方式）。
4. 比较中间元素与目标值： 如果arr[mid]等于目标值，则查找成功，返回mid。如果arr[mid]大于目标值，则说明目标值在左半部分，arr[mid]将不会再需要处于搜索区间内了（因为arr[mid]已经一定不等于target了）,并且right一直不在搜索范围内，所以将查找范围更新为[left, mid)，right = mid。 如果arr[mid]小于目标值，则说明目标值在右半部分,且arr[mid]将不会再需要处于搜索区间内了（因为arr[mid]已经一定不等于target了），但是left必须在搜索区间内，所以将查找范围更新为[mid+1, right]，left = mid + 1。
5. 重复步骤2和步骤3：直到找到目标值或查找范围为空（即left >= right），如果查找范围为空，则说明目标值不存在于数组中。

public static int binarySearch(int[] arr, int target) {  
        int left = 0;  
        int right = arr.length;  
  
        while (left < right) {  
            int mid = left + (right - left) / 2; // 防止溢出，同时更准确地找到中间位置  
            if (arr[mid] == target) {  
                return mid; // 找到目标元素，返回索引  
            } else if (arr[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
17
18

3. 范围查找

        有些时候，target不一定存在于序列中，但是我们想要得到大于target的序列区间，小于等于target的序列区间 或者 大于等于target的序列区间，小于target的序列区间。为了便于讨论，下面将循环条件定义为while（left <= right），指针移动方向为right = mid - 1，left = mid + 1。

        由于定义区间为【left，right】，left <= right，搜索到最后left肯定会等于right，此时mid = left = right，下一次移动后将不满足循环条件退出。最后一次是left移动还是right移动？将直接影响最终查找的范围，即等于号归left区间还是right区间。假设代码如下:

while(left <= right){
    int mid = left + (right - left)/2;
    if(nums[mid] > target){//这里需要重点考虑，如果有等号存在，则说明如果mid所指就是target，则哪个指针继续跳一个单位，它就必不会等于mid，对应的区间中也就不会出现等于taget的情况
    //区间【left，n】所指向的值均 >target，区间【0，right】所指向的值均 <= target
        right = mid + 1;
    }else{
        left = mid - 1;
    }
}
return left;
1
2
3
4
5
6
7
8
9
10

        可以自行验证，如果target不在序列中，最终left将指向第一个大于target的元素，right将指向最后一个小于target的元素。举例如下:

假设，序列{.....2,3,4,5.......}， target = 3.5，mid = left = right指向4，
此时target小于mid，之后执行right = mid - 1，right指向3，left仍指向4。
nums[【left，n】 ]  > target , nums[ 【0，right】 ] < target

假设，序列{.....2,3,4,5.......}， target = 4.5，mid = left = right指向4，
此时target大于mid，之后执行left = mid + 1，left指向5，right仍指向4
依然是nums[【left，n】 ]  > target , nums[ 【0，right】 ] < target

如果target存在于序列中，则最后执行right = mid - 1还是left = mid + 1将会影响target放入哪一个区间中。
1
2
3
4
5
6
7
8
9

        如果target存在于序列中，则mid最后所指就是target，所以最后一次移动指针之前，mid = left = right所指向的值就是target，此时哪个指针继续跳一个单位，它就必不会再有机会等于mid等于target，所以其对应的区间中也就不会出现等于taget的情况。
        因此上述 if 判断条件中的等号是否存在决定了是right指针会向左移动一格（此时，区间【left，n】所指向的值均 >=target，区间【0，right】所指向的值均 < target），还是left指针向右移动一格（此时，区间【left，n】所指向的值均 >target，区间【0，right】所指向的值均 <= target）

while(left <= right){
    int mid = left + (right - left)/2;
    if(nums[mid] >= target){//区间【left，n】所指向的值均 >=target，区间【0，right】所指向的值均 < target
        right = mid + 1;
    }else{
        left = mid - 1;
    }
}
return left;
1
2
3
4
5
6
7
8
9

总结

left指向第一个符合if中判断条件的元素，right指向最后一个不符合if中判断条件的元素

• 当判断条件为if(nums[mid] > target)时，最终nums[【left，n】 ] > target , nums[
  【0，right】 ] <= target;
• 当判断条件为if(nums[mid] >= target)时，最终nums[【left，n】 ] >= target , nums[
  【0，right】 ] < target;

这种范围查找也非常适合在遇到元素重复出现，需要找到重复元素的第一个元素或者重复元素的最后一个的位置索引。