二分查找

二分查找的就像我们喝酒时候猜数字一样，如 100 中猜一个数字 28

甲: 请猜我心里想的数字(28)，范围是 1 到 100
乙: 比 50 大还是小 (1-50)
甲: 小
乙: 比 25 大还是小 (1-25)
甲: 大
乙: 比 37 大还是小 (26-49)
甲: 小
乙: 比 37 大还是小 (26-37)
甲: 小
乙: 比 31 大还是小 (26-37)
甲: 小
乙: 是不是 28 (26-31)
甲: 对

如果用遍历查找的话需要 100 次， 用二分法 6 次， 最多 7 次就可以猜到

简单的二分法 (没有考虑重复数字)

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

来源：力扣（LeetCode）https://leetcode-cn.com/problems/binary-search

class Solution(object):
    def search(self, nums, target):
        low, high = 0, len(nums)-1
        # 注意是小于等于
        while low <= high:
            mid = low + (high-low)//2
            if nums[mid] == target:
                # 找到了目标, 不用考虑重复的话就可以直接返回 mid 了
                return mid
            elif nums[mid] > target:
                # 目标在中间位置的左边，改变最高位的位置
                high = mid - 1
            else:
                # 目标在中间位置的右边，改变最低位的位置
                low = mid + 1
        return -1

二分法进阶 (要考虑重复数字，找到特定数字的第一个或则最后一个)

请实现有重复数字的升序数组的二分查找
给定一个 元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的第一个出现的target，如果目标值存在返回下标，否则返回 -1

来源：牛客（LeetCode）

分析一下有什么不一样

如果二分法第一次找到了目标数字，这个数字可能是第一个，可能是第 N 个，也可能是最后一个, 怎么找到题目中要求的第一个呢
答案是: 缩小 high 的范围继续找，即

index = -1
if nums[mid] == target:
    index = mid
    high = mid - 1

重复整个过程就会找到第一个特定的数字了

class Solution(object):
    def search(self, nums, target):
        index, low, high = -1, 0, len(nums)-1
        while low <= high:
            mid = low + (high-low)//2
            if nums[mid] == target:
                index = mid
                high = mid - 1
            elif nums[mid] > target:
                # 继续找 mid 的左边
                high = mid - 1
            else:
                # 继续找 mid 的右边
                low = mid + 1
        return index

思考：怎么找第 N 个或则最后一个 target 呢