使用二分查找有一个前提条件：要查找的数必须在一个有序数组里。在这个前提下，取中间位置数作为比较对象：

• 若要查找的值和中间数相等，则查找成功。

• 若小于中间数，则在中间位置的左半区继续查找。

• 若大于中间数，则在中间位置的右半区继续查找。

不断重复上述过程，直到查找成功，或者查找区域变为 0，查找失败。

接下来通过具体例子来说明：

从数组 [5，8，15，17，25，30，34，39，45，52，60] 中查找元素 17 。

图解：

1. 初始化 low = 0，high = len(s) - 1 = 10， middle = ( low + high ) // 2 = 5
   
2. s[middle] > 17, high = mid -1 = 4，middle = ( low + high ) // 2 = 2
   
3. s[middle] < 17, low = middle + 1 = 3, middle = ( low + high ) // 2 = 3
   
4. 此时 s[middle] = 17，查找结束。

代码实现：

def binary_search(arr, target):
	low, high = 0, len(arr) -1
	
	while low <= high:
		mid = low + (high - low) // 2
		if arr[mid] == target:
			return mid
		elif arr[mid] < target:
			low = mid + 1
		else:
			high = mid -1

注意事项：

1. while 循环条件是 low <= high，而不是 low < high

   首先要明确的一点是，当前二分查找的区间是 [low, high]。每次在区间进行查找，找到目标值结束，查找成功；或者区间为 0 时结束，查找失败。当 low = high 时，[low, low] 的区间长度为 1，并不为空，这个时候结束循环会导致索引为 low 的元素没有被查找到。

2. mid 取值

   mid 取值时，一般可能会使用 (low + high) // 2，但是当 low 和 high 都很大时，low + high 可能会超出整数类型的范围，导致溢出，从而使 mid 取值错误。所以，在二分查找算法中，更安全的做法是使用 low + (high - low) // 2 来计算中间索引 mid。

3. low 和 high 取值

   以 low 来举例，low = mid + 1 而不是 low = mid，这是因为在 [low, high] 区间进行查找的过程中，已经确定下标为 mid 的元素不等于 target 的情况下，下一步需要查找的区间应该是 [mid + 1, high]，因为 mid 已经比较过了。

时间复杂度：

使用 T(n) 表示 n 个元素的二分查找算法时间复杂度。

当 n = 1 时，需要一次比较来确认这个元素是不是目标值，T(n) = O(1)

当 n > 1，特定元素和中间位置元素比较，需要 O(1)时间，如果比较不成功，那么需要在前半部分或后半部分搜索，问题的规模缩小了一半，时间复杂度变为 T(n/2)。假设最差需要比较 x 次，此时 T(n) = T(n/2^x) + xO(1)

最终区间的规模为 1，令 n/2^x = 1，x = log₂n，则 T(n) = T(1) + log₂nO(1) = O(1) + log nO(1) = O(log n)