二分搜索算法的基本思想是：每次比较中间元素与目标元素，如果相等则找到；如果中间元素小于目标元素，则在右半部分继续搜索；如果中间元素大于目标元素，则在左半部分继续搜索。这个过程不断重复，直到找到目标元素或者搜索区间为空。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def biSearch(nums, target, start, end):
    if start == end:
        if target > nums[end]:
            return end + 1
        if target < nums[start]:
            return start
        return start
    if start == end - 1 and nums[start] < target < nums[end]:
        return end
    middle = (start + end) // 2
    if nums[middle] == target:
        return middle
    elif nums[middle] < target:
        return biSearch(nums, target, middle + 1, end)
    else:
        return biSearch(nums, target, start, middle)

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        return biSearch(nums, target, 0, len(nums) - 1)