了解二分查找的里里外外

基本二分查找

在有序数组中查找一个元素，我们常常使用二分法进行查找。

理解二分法很简单，但是写对一个二分查找并不容易，边界问题是最大难题。

二分查找：

从数组nums中找到目标值target，返回其下标，没有则返回-1

从数组中找到一个中点mid

• 如果nums[mid] = target，则返回
• 如果nums[mid] > target，则从左边区间寻找
• 如果nums[mid] < target，则从右边区间寻找

先来看一个朴素的二分查找

int binary_search(std::vector<int>& nums, int target)
{
    int left = 0;
    int right = nums.size() - 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] < target) {
            left = mid + 1;
        }
    }
    return -1;
}

二分查找的逻辑是比较简单的，容易出问题的地方在于边界的细节。

• 左右边界的初始化值
  • 这里特别值有边界的初始化值 right = nums.size() - 1 还是right = nums.size()
• while循环跳出条件
  • while (left < right)还是while (left <= right)
• mid中值设定
  • mid = (left + right) / 2还是mid = (left + right + 1) / 2
• 区间收缩
  • left = mid 还是left = mid + 1
  • right = mid 还是right = mid - 1
• 结束特殊处理
  • 对于最后结果的异常处理

初始值与while条件

初始值选择两者皆可，按习惯来就行

while条件选择：

我们需要关注跳出循环的时机，while结束时是否对所有元素都进行了处理

初始值left, right为闭区间[0, size-1] 使用 while (left <= right)跳出循环时已经处理完了所有元素

初始值left right为闭区间[0, size-1]使用 while (left < right)跳出循环时:

1. 找到目标元素， 没问题
2. left == right ，没有处理最后一个元素，当最后一个元素是target时出现问题

比如初始数组为 nums= {1}, target = 1就会遗漏，解决方案是对最后一个元素进行处理：

int binary_search(std::vector<int>& nums, int target)
{
    int left = 0;
    int right = nums.size() - 1;
    while (left < right) {
        // ...
    }
    return nums[left] == target ? left : -1;
}

初始值left, right 为开区间[0, size)，使用while (left < right)跳出循环时：

1. 找到目标元素， 没问题
2. 当left >= right跳出循环 ，已处理完所有元素

初始值left, right 为开区间[0, size)，使用while (left <= right)跳出循环时：

1. 找到目标元素， 没问题
2. left == right 可能会越界，即收缩到右边界时，比如找一个大于数组中最大值的target，会导致越界，但是leetcode能pass，需要注意。

总结以上：

• 当区间为[0, size-1] 可使用while (left <= right) 或 while (left < right) + 特殊处理
• 当区间为[0, size) 可使用 while (left < right)， 使用while (left <= right)可能会越界。

如何正确收缩边界？

区间和mid

mid 的计算方式有两种

• mid = (left + right) / 2
• mid = (left + right + 1) / 2

这两种计算方式的区别是：元素个数为偶数时，mid取左还是右

对于闭区间形式，二者皆可，

对于开区间形式，只能使用mid = (left + right) / 2，因为第二种方式可能导致越界

区间和收缩

区间有开区间和闭区间，收缩方式有

• 左边收缩
  • left = mid + 1
  • right = mid
• 右边收缩
  • left = mid
  • right = mid - 1
• 两边同时收缩
  • left = mid + 1
  • right = mid - 1

闭区间方式 [0, size-1] 适应三种方式，收缩过程不会遗漏元素

开区间方式 [0, size) left 含义为 起始元素指针，right含义为末尾元素指针 + 1

在判定 nums[mid] 后，右侧收缩使用right = mid - 1意味着 区间收缩为[left, mid - 1)，导致nums[mid-1]元素被遗漏，尽管我们能进行特殊处理，对最后元素进行判定，但这种方式并不推荐。

因此开区间方式常常使用左边收缩

mid与收缩

循环中关键的一点是：保证能跳出循环，即无死循环）

在此例子中，必须保证每次都进行了收缩，也就是每一次区间必须与上一次不相同

当判定收缩左边界时，left边界收缩前后必须不同

当判定收缩右边界时，right边界收缩前后必须不同

mid = (left + right) / 2

假设收缩左边界方式为 left = mid + 1

left_2 = (left_1 + right) / 2 + 1;
设 right = left_1 + n;  n>=0
left_2 = (left_1 + left_1 + n) / 2 + 1;
left_2 = left_1 + n/2 + 1;
可得
    left_2 != left_1
收缩有效

假设收缩左边界方式为 left = mid

left_2 = (left_1 + right) / 2;
设 right = left_1 + n;  n>=0
left_2 = (left_1 + left_1 + n) / 2;
left_2 = left_1 + n/2; // n/2向下取整
当 n = 0 或 n = 1 即(left=right) 或 left = right - 1时， left_2 = left_1;
此时继续左边界收缩无效

假设收缩右边界方式为right = mid - 1

right_2 = (left + right_1) / 2;
设 left = right_1 - n;  n>=0
right_2 = (right_1 + right_1 -n) / 2 - 1;
right_2 = right_1 - n/2 -1; // n/2 上取
	可得 right_2 != right_1
	收缩有效

假设收缩右边界方式为 right = mid

right_2 = (left + right_1) / 2;
设 left = right_1 - n;  n>=0
right_2 = (right_1 + right_1 -n) / 2;
right_2 = right_1 - n/2; // n/2 上取
当 n = 0 即(left=right) 时， left_2 = left_1;
此时继续右边界收缩无效

同理可得：

当mid = (left+right+1)/2

收缩左边界方式为 left = mid left = right时无效

收缩左边界方式为 left = mid -1 , 有效

收缩右边界方式为right = mid - 1; 收缩有效

收缩右边界方式为right = mid; 当(left=right) 或 left = right - 1 时收缩无效

问题变得非常复杂了，现在我们要整合之前的逻辑

一般使用的是三种绿色的方式，现在应该非常清晰了

寻找左侧边界的二分查找

找左侧二分唯一要处理的就是nums[mid] == target，这时候继续往左边寻找，即收缩右边界

最后就是判断是否找到了

// 开区间
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size();
        while (left < right) {
            int mid = (left + right) / 2;
             if (nums[mid] >= target) {
                right = mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            }
        }
        if (left == nums.size()) return -1;
        return nums[left] == target ? left : -1;
    }
};

// 闭区间
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
             if (nums[mid] >= target) {
                right = mid - 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            }
        }
        if (left == nums.size()) return -1;
        return nums[left] == target ? left : -1;
    }
};

寻找右侧边界的二分查找

// 开区间
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size();
        while (left < right) {
            int mid = (left + right) / 2;
             if (nums[mid] > target) {
                right = mid;
            } else if (nums[mid] <= target) {
                left = mid + 1;
            }
        }
        if (left == 0) return -1;
        return nums[left-1] == target ? left : -1;
    }
};

// 闭区间
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
             if (nums[mid] > target) {
                right = mid - 1;
            } else if (nums[mid] <= target) {
                left = mid + 1;
            }
        }
        if (right < 0) return -1;
        return nums[right] == target ? left : -1;
    }
};

二分查找的应用条件

二分查找最基本是用来做有序数组的查找，似乎给出的结论是：单调是使用二分的必要条件。

考虑一个常见例子：

小明在图书馆借了很多书，过安检时候报警器响了，已知有一本书没有成功借到，如何快速找到这本书？

二分法是常见的办法，分成两堆，每次扫描其中一堆，再进行分堆。。。

这些书是有序的吗？显然并不是，那么二分的条件是什么呢？

答案是：分堆后能找到目标在哪一堆中。

https://leetcode-cn.com/problems/search-in-rotated-sorted-array/

搜索旋转排序数组便是典型

第一步：找到旋转点

第二步：对旋转点两边分别二分查找

因为旋转点和以数组首元素进行分隔，旋转点以左， >= 首元素， 旋转点以右， < 首元素

class Solution {
public:
    int search(std::vector<int>& nums, int target) {
        int rotate = search_rotate(nums, 0, nums.size());
        int res = binary_search(nums, 0, rotate, target);
        if (res == -1) {
            res = binary_search(nums, rotate, nums.size(), target);
        }
        return res;
    }

    int search_rotate(std::vector<int>& nums, int left, int right) {
        int rotate = 0;
        while (left < right) {
            int mid = (left + right) >> 1;
            if (nums[mid] >= nums[0]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        rotate = left % nums.size();
        return rotate;
    }

    int binary_search(std::vector<int>& nums, int left, int right, int target) {
        while (left < right) {
            int mid = (left + right) >> 1;
            if (nums[mid] >= target) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        if (left == nums.size()) return -1;
        return nums[left] == target ? left : -1;
    }
};

了解二分查找的里里外外

原文：https://www.cnblogs.com/yuhengshen/p/14699482.html