二分查找的对象是:有序数组。这点特别需要注意。要把数组排好序先。
基本步骤:
- 从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜素过程结束;
- 如果某一特定元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且跟开始一样从中间元素开始比较。
- 如果在某一步骤数组为空,则代表找不到。
这种搜索算法每一次比较都使搜索范围缩小一半。时间复杂度:O(logn)
1 | # 递归版本 |
-
局限性
- 数据结构必须是顺序表,也就是数组
- 数据必须有序
- 数据量太小不适合二分查找
- 比如10个数据,一次遍历就可以了
- 比如10个数据,一次遍历就可以了
- 数据量太大也不适合
- 因为数据必须以连续内存的形式存储在 memory 当中
二叉搜索的四种变形
变体1,查找第一个值等于给定值的元素
1 | def binarySearch(nums,key,low,high): |
变体2, 查找最后一个值等于给定值的元素
1 | def binarySearch2(nums,key): |
变体3,查找第一个大于等于给定值的元素
1 | def binarySearch3(nums,key,low,high): |
变体4,查找第一个小于等于给定值的元素
1 | def binarySearch4(nums,key): |
变体5,查找第一个比某元素大的元素
1 | def find_first_big(nums,key): |