iicey

算法思想

二分法查找适用于数据量较大时，但是数据需要先排好顺序。主要思想是: (设查找的数组区间为array[low, high])

1. 确定该区间的中间位置K。
2. 将查找的值T与array[k]比较。若相等，查找成功返回此位置；否则确定新的查找区域，继续二分查找。
   区域确定如下：a.array[k]>T 由数组的有序性可知array[k,k+1,……,high]>T;故新的区间为array[low,……，K-1]b.array[k]<T 类似上面查找区间为array[k+1,……，high]。
   每一次查找与中间值比较，可以确定是否查找成功，不成功当前查找区间将缩小一半，递归查找即可。
   时间复杂度为:log2n，（是以2为底，n的对数）。

复杂度分析

时间复杂度

1. 最坏情况查找最后一个元素（或者第一个元素）Master定理T(n)=T(n/2)+O(1)所以T(n)=O(log2n)
2. 最好情况查找中间元素O(1)查找的元素即为中间元素（奇数长度数列的正中间，偶数长度数列的中间靠左的元素）

分析

因为二分查找每次排除掉一半的不适合值，所以对于n个元素的情况：

一次二分剩下：n/2
两次二分剩下：n/2/2 = n/4
…
m次二分剩下：n/(2^m)

在最坏情况下是在排除到只剩下最后一个值之后得到结果，即

n/(2^m)=1

所以由上式可得 ： 2^m=n

进而可求出时间复杂度为： log2(n)

正确示例

# -*- coding: utf-8 -*-

def binarySearch(alist, item):
    first = 0
    last = len(alist) - 1

    while first <= last:
        mid = (first + last) // 2
        print(f"while - first:{first} last:{last} mid:{mid} alist[mid]:{alist[mid]} item:{item}")
        
        if alist[mid] == item:
            return mid
        
        if alist[mid] > item:
            last = mid - 1
            print(f"> - first:{first} last:{last} mid:{mid} alist[mid]:{alist[mid]} item:{item}")
        else:
            first = mid + 1
            print(f"< - first:{first} last:{last} mid:{mid} alist[mid]:{alist[mid]} item:{item}")

    return -1

test = [0, 1, 2, 8, 13, 17, 19, 32, 42]
print(binarySearch(test, 8))

书中示例(错误)

numbers = [1, 3, 5, 6, 7, 8, 13, 14, 15, 17, 18, 24, 30, 43, 56]
head, tail = 0, len(numbers)  # 数组长度刚好是最大下标值+1
search = int(input("Enter a number to search:"))

while end - start > 1:  # 当尾指针tail减头指针head等于1时，查找范围内只head有指向的数
    mid = (head + tail) // 2  # mid存储中间数的下标，//2代表对/2的结果舍去分数部分取整
    if search < numbers[mid]:  # search是我们要搜索的元素，如果它小于mid指向的元素
        tail = mid
    if search > numbers[mid]:  # 如果search小于mid指向的元素
        start = mid + 1  # mid指向的元素小于search，所以不用把它保留在范围内
    if search == numbers[mid]:
        ans = mid
        break  # 找到元素的话就直接结束
else:
    if search == numbers[head]:
        ans = head
    else:
        ans = -1  # 如果数组中没有这个元素，那么输出-1
print(ans)