python代码练习：二分查找法

题目一：

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

方法一：左闭右闭区间

from typing import List
class Solution:
    def search(self,nums:List[int],target:int)->int:
        low,high=0,len(nums)-1

        while  low<=high:
            middle = (low+high)//2
            # 在while时区间右闭已取nums[middle],接下来的区间判断不需要包含nums[middle]，所以high边界取middle-1
            if target < nums[middle]:
                high = middle-1
            elif target > nums[middle]:
                low = middle+1
            else:
                return middle
        return -1

if __name__ == '__main__':
    s = Solution()
    print(s.search(nums=[-1,0,3,5,9,12],target=9))
    print(s.search(nums=[-1,0,3,5,9,12],target=2))

方法二：左闭右开区间

from typing import List


class Solution:
    def search(self, nums: List[int], target: int) -> int:
        low, high = 0, len(nums)        

        while low < high:
            middle = (low + high) // 2
            # 在while时区间右开未取nums[middle],接下来的区间判断需要包含nums[middle]，所以high边界取middle
            if target < nums[middle]:
                high = middle
            elif target > nums[middle]:
                low = middle + 1
            else:
                return middle
        return -1


if __name__ == '__main__':
    s = Solution()
    print(s.search(nums=[-1, 0, 3, 5, 9, 12], target=9))
    print(s.search(nums=[5], target=5))

其他：

• typing用法
• 什么是二分查找

题目二：

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

from typing import List
class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        low,high=0,len(nums)-1
        while low<=high:
            middle = (low+high)//2
            if target<nums[middle]:
                high = middle-1
            elif target>nums[middle]:
                low = middle+1
            else:
                return middle
        return high+1

if __name__ == '__main__':
    s=Solution()
    print(s.searchInsert(nums=[1,3,4,5,6],target=5))
    print(s.searchInsert(nums=[1,3,4,5,6],target=0))
    print(s.searchInsert(nums=[1,3,4,5,6],target=9))
    print(s.searchInsert(nums=[],target=9))