二分查找

发表于 | 分类于 |

二分查找的基本思路就是每次都取中间，如果等于目标，则返回结果。否则，判断目标值与中间值的大小关系，选择丢弃掉一半的元素，再继续执行二分查找。时间复杂度是 O(logN) ，空间复杂度是 O(1) 。

图示：

核心代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def binarySearch(A, target):
    
    start = 0
    end = len(A) - 1

    # 循环判断，直到找到target或者是start > end
    while start <= end:
        mid = (start + end) / 2

        # 返回结果
        if A[mid] == target:
            return mid
        # 舍弃掉左半部分
        if A[mid] < target:
            start = mid + 1
        # 舍弃掉右半部分
        else:
            end = mid - 1

    return end