请注意,本文编写于 788 天前,最后修改于 687 天前,其中某些信息可能已经过时。
面试中的二分查找
描述二分查找
手写二分查找
考察查找次数
二分查找用于快速索引一个元素的位置,假设有一个已经排好序的数组,我们取中间位置跟目标元素比较,目标元素大,往右继续找中间,目标元素小,往左继续找中间。
算法描述
- 前提:已有排序数组 A(假设已经做好)
- 定义左边界 L、右边界 R,确定搜索范围,循环执行二分查找(3、4两步)
- 获取中间索引
M = Floor((L+R) /2)
中间索引的值 A[M] 与待搜索的值 T 进行比较
- A[M] == T 表示找到,返回中间索引
- A[M] > T,中间值右侧的其它元素都大于 T,无需比较,中间索引左边去找,M - 1 设置为右边界,重新查找
- A[M] < T,中间值左侧的其它元素都小于 T,无需比较,中间索引右边去找, M + 1 设置为左边界,重新查找
- 当 L > R 时,表示没有找到,应结束循环
public class BinarySearch {
public static void main(String[] args) {
int[] ints = {1, 5, 8, 9, 12, 15, 16, 19, 22, 44, 52, 66, 158};
int i = binarySearch(ints, 66);
System.out.println(i);
}
public static int binarySearch(int[] ints, int t) {
//左
int l = 0;
//右
int r = ints.length - 1;
//中间
int m;
while (l <= r) {
//m = (l + r) / 2; 可能内存溢出
m = (r - l) / 2 + l;
if (t > ints[m]) {
l = m + 1;
} else if (t < ints[m]) {
r = m - 1;
} else {
return m;
}
}
return -1;
}
}
问题:
- 有一个有序表为 1,5,8,11,19,22,31,35,40,45,48,49,50 当二分查找值为 48 的结点时,查找成功需要比较的次数
- 使用二分法在序列 1,4,6,7,15,33,39,50,64,78,75,81,89,96 中查找元素 81 时,需要经过( )次比较
- 在拥有128个元素的数组中二分查找一个数,需要比较的次数最多不超过多少次
算剩下元素个数/2,结果是奇数则+1,找到这个位置进行比较,偶数不变。
- 13个元素,13/2 = 6(舍去小数) 找第7个,31 < 48,往右算剩下6个元素,6/2 = 3 继续找第3个,45 < 48,剩下3个,找第2个,49 > 48 找左边,剩下一个(根据上面的算法代码这里要比最后一次!!!)一共4次,另外二分查找还有别的算法,可能只需要比3个,道理也很简单。
- 14个元素,第7个,39 < 81,剩下7个,找第4个,75 < 81,剩下3个,找第2个,89 > 81,左边一个比最后一次。一共4次。
- 2^n = 128,算 n 即可。计算器中只能算10为底的对数,可以用换底公式,$$n = log_2N = log_{10}N/log_{10}2$$
版权属于:乐心湖's Blog
本文链接:https://www.xn2001.com/archives/666.html
声明:博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!