Binery Search-二分

应用场景：

寻找一个数、寻找左侧边界、寻找右侧边界

解题思路：

• 二分查找算法是典型的「减治思想」的应用，我们使用二分查找将待搜索的区间逐渐缩小，以达到「缩减问题规模」的目的；
• 掌握二分查找的两种思路：
  • 思路 1：在循环体内部查找元素：while (left <= right)；
  • 思路 2：在循环体内部排除元素：while (left < right)。
• 全部使用左闭右闭区间，不建议使用左闭右开区间，反而使得问题变得复杂；
• 不建议背模板，每一步都要清楚为什么这样写，不要跳步，更不能想当然。

计算 mid 时需要技巧防止溢出，建议写成: mid = left + (right - left) / 2
不要出现 else，而是把所有情况用 else if 写清楚，这样可以清楚地展现所有细节

在循环体内部查找元素（解决简单问题时有用）

例：搜索一个数字，如果存在，返回其索引，否则返回 -1。

class Solution:
    def search(self, nums, target):
        nums.sort()  # 排序；倒序   nums.sort(reverse = True)
        l = len(nums)
        if l == 0:
            return -1
        left = 0
        right = l - 1
        while left <= right:
            mid = int(left + (right - left)/2)
            if nums[mid] == target:
                return mid
            elif nums[mid] > target:      # 下一轮搜索[left,mid-1]
                right = mid - 1
            else:
                left = mid + 1       # 下一轮搜索[mid+1,right]
        return -1
s = Solution()
t = s.search([3, 5, 2, 1], 3)
print(t)

python 中扩展/ // %

在pyhon3中/是真除法。
3/2=1.5
取整数位//
3//2=1
%表示求余数
5%2=1

例如：寻找左、右侧边界的二分搜索对比

# 搜索一个数
int binarySearch(int[] nums, int target) {
    int left = 0; 
    int right = nums.length - 1; // 注意
    while(left <= right) { // 注意
        int mid = (right + left) / 2;
        if(nums[mid] == target)
            return mid; 
        else if (nums[mid] < target)
            left = mid + 1; // 注意
        else if (nums[mid] > target)
            right = mid - 1; // 注意
        }
    return -1;
}
# 寻找左边界
int left_bound(int[] nums, int target) {
    if (nums.length == 0) return -1;
    int left = 0;
    int right = nums.length; // 注意
    while (left < right) { // 注意
        int mid = (left + right) / 2;
        if (nums[mid] == target) {
            right = mid;  
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid; // 注意
        }
    }
    return left;
}
寻找右侧边界
int right_bound(int[] nums, int target) {
    if (nums.length == 0) return -1;
    int left = 0
    right = nums.length;
    while (left < right) {
        int mid = (left + right) / 2;
        if (nums[mid] == target) {
            left = mid + 1; // 注意
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid;
        }
    }
    return left - 1; // 注意