二分查找（Binary Search），也称折半查找，是一种在有序数组中查找特定元素的搜索算法。基本思想是在每次查找中，将待查关键字与查找区间的中间元素进行比较，从而将查找区间减半，直到找到目标元素为止。
二分查找的时间复杂度为 O(log n)，比直接查找时间复杂度 O(n) 更低效，所以在海量数据的情况下，使用二分查找能大幅提高查找速度，是一种十分实用的查找算法。
二分查找的实现方式有多种，常见的有递归和非递归两种。非递归实现方式相对简单，通常使用循环语句来进行实现。例如，在一个有序数组 arr 中查找元素 x 可以采用以下代码：
def binarySearch(arr, x): l = 0 r = len(arr)-1 while l