二分查找 - 掘金

二分查找实现

    def bsearch(self, nums, target):
        low, high = 0, len(nums)
        while low <= high:
            middle = low + ((high - low) >> 1)
            if nums[middle] == target:
                return True
            elif nums[middle] > target:
                high = middle - 1
            else:
                low = middle + 1
        return False

递归实现

    def binaySearch(self, nums, target):
        return self.bsearchInternally(nums, 0, len(nums) - 1, target)

    def bsearchInternally(self, nums,low, high, target):
        if low > high: return False
        mid = low + ((high - low) >> 1)
        if nums[mid] == target:
            return True
        elif nums[mid] > target:
            high = mid - 1
        else:
            low += 1
        return self.bsearchInternally(nums, low, high, target)

1. 循环退出条件

low <= high

2. mid的取值

mid = (low + high) // 2, 当low 和 high比较大时候, 两者之和可能会溢出, 改进写法 mid = low + (high - low) // 2, 优化写法mid = low + ((high - mid)>>1)

3.low 和 high 更新

low = mid + 1, high = mid - 1

二分查找应用场景

1. 二分查找依赖顺序表结构, 数组

2. 针对有序数据

3. 数据太小不适合二分查找

4. 数据太大也不适合

二分查找变形

查找第一个值等于给定值的元素

    def bsearch(self, nums, target):
        low, high = 0, len(nums) - 1
        while low <= high:
            mid = low + ((high - low) >> 1)
            if nums[mid] > target: high = mid - 1
            elif nums[mid] < target: low = mid + 1
            else:
                if mid == 0 or nums[mid - 1] != target: return mid
                high = mid - 1
        return -1

查找最后一个值等于给顶元素

    def bsearchLast(self, nums, target):
        low, high = 0, len(nums) - 1
        while low <= high:
            mid = low + ((high - low) >> 1)
            if nums[mid] > target:
                high = mid - 1
            elif nums[mid] < target:
                low = mid + 1
            else:
                if mid == len(nums) - 1 or nums[mid + 1] != target: return mid
                low = mid + 1
        return -1

查找第一个大于等于给定值的元素

    def bsearchFirst(self, nums, target):
        low, high = 0, len(nums) - 1
        while low <= high:
            mid = low + ((high - low) >> 1)
            if nums[mid] >= target:
                if mid == 0 or nums[mid - 1] < target: return mid
                else:
                    high = mid - 1
            else:
                low = mid + 1
        return -1

查找最后一个小于等于给定值的元素

    def bsearchLastSmallOrEqual(self, nums, target):
        low, high = 0, len(nums) - 1
        while low <= high:
            mid = low + ((high - low) >> 1)
            if nums[mid] > target:
                high = mid - 1
            else:
                if mid == len(nums) - 1 or nums[mid + 1] > target: return mid
                low = mid - 1
        return -1