比较次数少，查找速度快，平均性能好

  • 从数组的中间元素开始查找;
  • 如果中间元素正好是要查找的元素,则搜索过程结束;
  • 如果中间元素大于或小于要查找元素,则在小于或大于中间元素的那一半进行搜索，并且从中间元素开始比较;
  • 如果在某一步骤数组为空,则代表找不到;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
"""
二分查找
Copyright ©conghaoyuan@gmail.comm
"""
class BinarySearch:

    def __init__(self) -> None:
        pass

    def OneDimSearch(self, lists, item):
        length = len(lists)
        start = 0
        end = length - 1
        while start <= end:
            mid = (start + end) // 2
            if lists[mid] > item:
                end = mid - 1
            elif lists[mid] < item:
                start = mid + 1
            else:
                return True
        return False
    
    def TwoDimSearch(self, lists, item):
        pass


if __name__ == '__main__':
    bs = BinarySearch()
    li = [1, 3, 5, 6, 7, 9, 10, 12, 14, 15]
    print(bs.OneDimSearch(li, 4))
    print(bs.OneDimSearch(li, 5))