摘要：所以，二分查找较适用于一次排序，多次查找的数据。面对大量的数据，二分查找方能体现其优势。
1. 二分查找的思想
二分查找是一种使用十分普遍的查找算法，其基本的思路也非常的简单，在一个有序的数据集合中，我们想要查找某个数据，直接取最中间的那个数据，将它和要找的数据进行比较，如果较大，则在更大的那个数值区间继续取中间值查找，反之亦然。
例如我们要在一个有序的集合里[1，3，5，6，7，8，10]，查找5这个值，那么二分查找的过程就如下图所示，经过三次查找操作就能够找到。
2. 二分查找的实现
相信你已经能够理解二分查找的思路了，接下来看看它的代码实现。其实根据思路不难看出，二分查找有点分治的思想，所以代码可以用递归实现，也可以用循环实现。
二分查找的递归实现：
public class BinarySearch {
public static int binarySearchByRecursion(int[] data, int value) {
return binarySearchInternally(data, 0, data.length - 1, value);
}
private static int binarySearchInternally(int[] data, int low, int high, int value) {
while (low <= high){
//计算中间值
int mid = low + ((high - low) >> 1);
if (data[mid] == value) return mid;
else if (data[mid] < value) return binarySearchInternally(data, mid + 1, high, value);
else return binarySearchInternally(data, low, mid - 1, value);
}
return -1;
}
}
二分查找循环实现：
public static int binarySearchByCircle(int[] data, int value) {
int low = 0;
int high = data.length - 1;
while (low <= high){
//计算中间值
int mid = low + ((high - low) >> 1);
if (data[mid] == value) return mid;
else if (data[mid] < value) low = mid + 1;
else high = mid - 1;
}
return -1;
}
3. 二分查找的局限性
二分查找是一种很高效的算法，时间复杂度为 O(logn)，要是使用上的话，非常的方便。但是，二分查找对数据的要求也十分严苛。
首先，二分查找只适用于顺序表结构，说简单点，就是数组。因为可以利用数组下标访问的特性，快速取出数据进行比较。其他的数据结构例如链表，如果使用二分查找的话，不能进行下标访问，每次比较都必须遍历链表寻找中间节点，时间复杂度就很高了。
其次，二分查找针对的是有序数组，如果数据未排序，则必须进行排序才能够使用，前面说到了，排序的时间复杂度一般为 O(nlogn)。所以，二分查找较适用于一次排序，多次查找的数据。如果数据的插入和删除操作过于频繁，那么维护有序的成本就很高。
最后，二分查找适用于数据量较大的场景，假如我们要在几十或者几百个数据中进行查找，那直接遍历查找即可。面对大量的数据，二分查找方能体现其优势。
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/73858.html
摘要：为检查长度为的列表，二分查找需要执行次操作。最后需要指出的一点是高水平的读者可研究一下二叉树关于二叉树，戳这里数据结构与算法二叉树算法常见练习在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。 常见数据结构 简单数据结构（必须理解和掌握） 有序数据结构：栈、队列、链表。有序数据结构省空间（储存空间小） 无序数据结构：集合、字典、散列表，无序...
摘要：为检查长度为的列表，二分查找需要执行次操作。最后需要指出的一点是高水平的读者可研究一下二叉树关于二叉树，戳这里数据结构与算法二叉树算法常见练习在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。 常见数据结构 简单数据结构（必须理解和掌握） 有序数据结构：栈、队列、链表。有序数据结构省空间（储存空间小） 无序数据结构：集合、字典、散列表，无序...
摘要：为检查长度为的列表，二分查找需要执行次操作。最后需要指出的一点是高水平的读者可研究一下二叉树关于二叉树，戳这里数据结构与算法二叉树算法常见练习在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。 常见数据结构 简单数据结构（必须理解和掌握） 有序数据结构：栈、队列、链表。有序数据结构省空间（储存空间小） 无序数据结构：集合、字典、散列表，无序...
摘要：通过两个二分查找的条件继续进行问题的分析，那么问题又来了，二分查找是快速的查找一个数据是否存在一组数据中，而且效率极高，亿查找一个数据只需次查找。二分查找的三点重点循环退出条件注意是而不是。 showImg(https://segmentfault.com/img/remote/1460000018761246);这篇文章主要深入数据结构与算法在解决实际问题怎么运用和分析的，对于 IP...
摘要：查找最后一个等于给定值的元素这种变形的二分查找和上面的这种情况很类似，还是利用上面的那个数组，我们要查找最后一个等于的元素。 1. 概述 前面说到了二分查找问题，看起来非常的简单，的确，前面的两种实现都不难，代码也很容易写，因为那只是最基础的二分查找问题了。今天来看看几种稍微复杂的二分查找问题： 查找第一个等于给定值的元素 查找最后一个等于给定值的元素 查找第一个大于等于给定值的元素...
阅读 2537·2023-04-26 00:57
阅读 909·2021-11-25 09:43
阅读 2220·2021-11-11 16:55
阅读 2203·2019-08-30 15:53
阅读 3592·2019-08-30 15:52
阅读 1457·2019-08-30 14:10
阅读 3379·2019-08-30 13:22
阅读 1209·2019-08-29 11:18
