二分查找的简单理解
2023-02-19 12:17:30 时间
详细描述
二分查找的搜索过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜索过程结束;如果某一特定元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空,则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。
二分查找详细的执行步骤如下:
- 在有序表中,取中间记录作为比较对象;
- 若给定值与中间记录的关键字相等,则查找成功;
- 若给定值小于中间记录的关键字,则在中间记录的左半区继续查找;
- 若给定值大于中间记录的关键字,则在中间记录的右半区继续查找;
- 不断重复步骤 1~4,直到查找成功,或所有查找区域无记录,查找失败为止。
算法图解
问题解疑
二分查找算法有哪些局限性?
二分查找算法需要按照下标随机访问。所以更适合数组结构,而不适合链表结构,数组按照下标随机访问数据的时间复杂度是 \(O(1)\),而链表随机访问的时间复杂度是 \(O(n)\)。
二分查找针对的是有序数。二分查找只能用在插入、删除操作不频繁,一次排序多次查找的场景中,针对动态变化的数据集合,二分查找将不再适用。
数据量太小不适合二分查找。在一个大小为 10 的数组中查找一个元素,不管用二分查找还是顺序遍历,查找速度都差不多,只有数据量比较大的时候,二分查找的优势才会比较明显。
数据量太大也不适合二分查找。二分查找是作用在数组这种数据结构之上的,太大的数据用数组存储比较吃力,也就不能用二分查找了。
二分查找算法有哪些变形?
- 查找第一个值等于给定值的元素
- 查找最后一个值等于给定值的元素
- 查找第一个大于等于给定值的元素
- 查找最后一个小于等于给定值的元素
代码实现
查找接口
package cn.fatedeity.algorithm.search;
public interface Search {
int search(int[] numbers, int target);
}
二分查找类
package cn.fatedeity.algorithm.search;
/**
* 二分查找类
*/
public class BinarySearch implements Search {
private int search(int[] numbers, int target, int left, int right) {
if (left > right) {
return -1;
} else if (left == right) {
if (numbers[left] == target) {
return left;
} else {
return -1;
}
}
if (target < numbers[left] || target > numbers[right]) {
return -1;
}
int mid = (left + right) >> 1;
if (numbers[mid] > target) {
return this.search(numbers, target, left, mid - 1);
} else if (numbers[mid] < target) {
return this.search(numbers, target, mid + 1, right);
} else {
return mid;
}
}
@Override
public int search(int[] numbers, int target) {
return this.search(numbers, target, 0, numbers.length - 1);
}
}
相关文章
- Jgit的使用笔记
- 利用Github Action实现Tornadofx/JavaFx打包
- 叹息!GitHub Trending 即将成为历史!
- 微软软了?开源社区讨论炸锅,GitHub CEO 亲自来答
- GitHub Trending 列表频现重复项,前后端都没去重?
- Photoshop Elements 2021版本软件安装教程(mac+windows全版本都有)
- (ps全版本)Photoshop 2020的安装与破解教程(mac+windows全版本都有)
- (ps全版本)Photoshop cc2018的安装与破解教程(mac+windows全版本,包括2023
- 环境搭建:Oracle GoldenGate 大数据迁移到 Redshift/Flat file/Flume/Kafka测试流程
- 每个开发人员都要掌握的:最小 Linux 基础课
- 来撸羊毛了!Windows 环境下 Hexo 博客搭建,并部署到 GitHub Pages
- 超实用!手把手入门 MongoDB:这些坑点请一定远离
- 【GitHub日报】22-10-09 zustand、neovim、webtorrent、express 等4款App今日上新
- 【GitHub日报】22-10-10 brew、minio、vite、seaweedfs、dbeaver 等8款App今日上新
- 【GitHub日报】22-10-11 cobra、grafana、vue、ToolJet、redwood 等13款App今日上新
- Photoshop 2018 下载及安装教程(mac+windows全版本都有,包括最新的2023)
- Photoshop 2017 下载及安装教程(mac+windows全版本都有,包括最新的2023)
- Photoshop 2020 下载及安装教程(mac+windows全版本都有,包括最新的2023)
- Photoshop 2023 资源免费下载(mac+windows全版本都有,包括最新的2023)
- 最新版本Photoshop CC2018软件安装教程(mac+windows全版本都有,包括2023