当前位置： 首页 >> 数据结构与算法 >> 二分查找

---

二分查找

2020-07-04 18:37:28 星期六  阅读：2012

---

二分查找针对的是一个有序的数据集合，查找思想有点类似分治思想。每次都通过跟区间的中间元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间被缩小为 0。比如，下图中通过7次就能“猜”出23在0-99范围内是否存在。 ####特点 - 惊人的查找速度：假设数据大小是n，每次查找后数据都会缩为原来的一半，所以时间复杂度是O(log2n)，也就是O(logn)，这是一种非常高效的时间复杂度，有的时候甚至比O(1)的算法还要高效。比如，n的大小是2^32时（大约42亿个元素），使用二分查找一个数据，最多只需要32次比较就能找到。 - 应用场景有限，底层必须依赖数组。 ####代码实现 以下代码给出最简单的二分查找的代码实现。所谓最简单，就是有序数组中不存在重复元素。 ``` def binary_search(arr, value): # 从arr里查找是否存在值为value的元素 high = len(arr) - 1 low = 0 while(low <= high): mid = (low + high) // 2 if arr[mid] == value: return True elif arr[mid] > value: high = mid - 1 else : low = mid + 1 return False ``` ####二分查找的局限 需要二分查找的数据结构应该为顺序表结构，也就是数组。因为链表使用下标访问时，时间复杂度是O(n)，而数组是O(1)； 二分查找针对的是有序的静态数据，无序的数据需要先排序；如果数据是动态（频繁删除、插入）的，则需要排序后才能二分查找。增加了性能消耗。 数据量太小不适合二分查找。因为数据量小时，直接使用遍历即可。 数据量太大也不适合用二分查找。因为二分查找是针对数组的，而数组在内存里是连续的内存地址，如果当前可用连续内存小于需要查找的数据，则用数组存储就成为了瓶颈。也就不能用二分查找了。 ####实例 如何在1000万个整数中快速查找出某个整数？内存限制是100MB， 每个整数占用8字节。 可以计算得出1000万个整数占用的内存时80MB，符合内存的限制。思路是：先把这1000万个整数排序，然后再采用二分查找算法来查找。 当然也可以用散列表和二叉树等动态的数据结构，但是使用这些数据结构，内存肯定超过100MB，但是数组是连续的内存空间，除了存储数据不需要存储额外的信息，所以可以在100MB的内存限制下正常工作。 ###4种常见的二分查找变形问题 ####查找第一个值等于给定值的元素 比如查找序列[1,3,3,3,5,6]中第一个出现3的数据。 ``` def binary_search_pro(arr, value): high = len(arr) - 1 low = 0 while ( low <= high ): mid = (high + low) // 2 if arr[mid] > value: high = mid - 1 elif arr[mid] < value: low = mid + 1 else: if mid == 0 or arr[mid -1 ] != value: # 如果数组里面前一个值不等于需要查找的值，则说明当前的值就已经是第一个 return mid else: high = mid - 1 # 如果mid前一个元素的值也是当前需要查找的值 ，则更新high为前一个元素的下标 return -1 ``` ####查找最后一个值等于给定值的元素 比如查找序列[1,3,3,3,5,6]中最后一个出现3的数据。 ``` def binary_search_pro(arr, value): high = len(arr) - 1 low = 0 while ( low <= high ): mid = (high + low) // 2 if arr[mid] > value: high = mid - 1 elif arr[mid] < value: low = mid + 1 else: # 看当前mi是最后一个元素，或者下一个元素是需要查找的元素，如果是，则更新low的值为下一个元素开始 # 如果下一个元素不是当前需要查找的数据，则说明当前的mid值已经是最后一个 if arr[mid] == len(arr) - 1 or arr[mid + 1 ] != value: eturn mid else: low = mid + 1 return -1 ``` ####查找第一个大于等于给定值的元素 比如，arr=[1,2,3,6,9,10,12]，需要从该arr中查找出第一个大于等于8的元素，正确的返回结果应该是4（即arr[4] = 9） ``` def binary_search_pro(arr, value): high = len(arr) - 1 low = 0 while ( low <= high ): mid = (low + high) // 2 if arr[mid] < value: low = mid + 1 # 只需要判断满足条件的情况，并返回即可，其他情况做额外处理 elif (arr[mid] >= value and arr[mid -1] < value) or mid == 0: return mid else: high = mid -1 # 如果前面一个元素的值也大于给定的value，则更新high = high -1 return -1 ``` ####查找最后一个小于等于给定值的元素 比如，arr=[1,2,3,6,9,10,12]，需要从该arr中查找出最后一个小于等于8的元素，正确的返回结果应该是3（即arr[3] = 6） ``` def binary_search_pro(arr, value): high = len(arr) - 1 low = 0 while ( low <= high ): mid = (low + high) // 2 if arr[mid] > value: high = mid - 1 # 这里需要注意的是mid == len(arr) - 1 这个条件要写在前面，要不然当mid = len(arr) - 1时就会数组下标就会越界 elif mid == len(arr) -1 or (arr[mid] <= value and arr[mid + 1] > value): return mid else: low = mid + 1 return -1 ```