[ 什么是二分查找 ]
二分查找又称为折半查找,该算法的思想是将数列按序排列,采用跳跃式方法进行查找,即先以有序数列的中点位置为比较对象,
如果要找的元素值小于该中点元素,则将待查序列缩小为左半部分,否则为右半部分。以此类推不断缩小搜索范围。
[ 二分查找的条件 ]
二分查找的先决条件是查找的数列必须是有序的。
[ 二分查找的优缺点 ]
优点:比较次数少,查找速度快,平均性能好;
缺点:要求待查数列为有序,且插入删除困难;
适用场景:不经常变动而查找频繁的有序列表。
[ 算法步骤描述 ]
① 首先确定整个查找区间的中间位置 mid = (min + max)/ 2
② 用待查关键字值与中间位置的关键字值进行比较:
i.
若相等,则查找成功;
ii. 若小于,则在前半个区域继续进行折半查找;
iii.若大于,则在后半个区域继续进行折半查找;
③ 对确定的缩小区域再按折半公式,重复上述步骤。
④ 最后得到结果:要么查找成功,要么查找失败。折半查找的存储结构采用一维数组存放。
[ Java实现 ]
public class BinarySearch {
public static int binarySearch(int[] arr, int target) {
if (arr != null) {
int min, mid, max;
min = 0; // the minimum index
max = arr.length - 1; // the maximum index
while (min <= max) {
mid = (min + max) / 2; // the middle index
if (arr[mid] < target) {
min = mid + 1;
} else if (arr[mid] > target) {
max = mid - 1;
} else {
return mid;
}
}
}
return -1;
}
// test case
public static void main(String[] args) {
int[] arr = { 1, 2, 3, 5, 6, 7, 8, 9, 23, 34 };
System.out.println(binarySearch(arr, 5));
System.out.println(binarySearch(arr, 23));
System.out.println(binarySearch(arr, 0));
System.out.println(binarySearch(arr, 35));
}
}
分享到:
相关推荐
二分法查找 *进行二分法查找的前提是数组已有序 *查找范围的上下界
写出二分法查找算法函数实现。
Java常用排序算法&程序员必须掌握的8大排序算法+二分法查找 Java常用排序算法&程序员必须掌握的8大排序算法+二分法查找
Java常用高效8大排序算法与二分法查找,适合正在学习算法和准备学习算法的算法爱好者和研究使用算法的开发人员使用。
二分法查找是一种常用的查找算法,也称为折半查找。...总之,二分法查找是一种常用的查找算法,适用于有序数组中查找某个元素的位置。通过将待查找区间缩小一半的方式,可以快速地定位目标元素,时间复杂度为O(log n)。
初学java的基础算法,巩固学习,面试常考的基础算法,自己面试被问了几次,所以总结出来给大家分享!!!!
Java常用排序算法源码 稳定:冒泡排序、插入排序、归并排序和基数排序;不稳定:选择排序、快速排序、希尔排序、堆排序
这是一个百度面试的题目,乱序给出从1到1000的999个数,其中有一个数丢失了,找出这个数,给出了3种解决方法,并给出的运行时间,对比了3种方案优劣
Java常用排序算法&程序员必须掌握的8大排序算法+二分法查找(同步到博客).doc
分别用递归和非递归方法实现二分查找算法 的完整程序,indexof()返回的是循环实现的二分法查找,getindex()实现的是递归算法实现的二分法查找。
主要介绍了Java使用二分法进行查找和排序的示例,二分插入排序和二分查找是基础的算法,需要的朋友可以参考下
主要介绍了java 二分法算法的实例的相关资料,希望通过本文大家能够掌握二分法,需要的朋友可以参考下
冒泡排序是最常用的排序算法,再笔试中也非常常见,能手写出冒泡排序可以说是基本的素养。 算法重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来,这样越大的元素会经由交换慢慢的...
插补查找法 * 其原理与二分法查找是相同的,搜寻的对象大于500时, * 比二分法查找速度快 * (K-K1)/(Ku-K1)=(m-1)/(u-1)
主要介绍了Java 二分法检索算法代码实现详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧
主要介绍了java 中二分法查找的应用实例的相关资料,希望通过本文大家能掌握二分法的使用方法,需要的朋友可以参考下
文章目录6.4 冒泡排序的基础算法6.4.1 冒泡排序优化算法6.5二分法查找(折半检索) 6.4 冒泡排序的基础算法 冒泡排序是常用的排序算法,笔试中非常常见。 算法重复地走访过排序的数列,一次比较两个元素,如果他们的...
java排序算法的比较....二分法查找示例....选择排序算法....可以看看
Java实现二分查找的递归和非递归算法
包含数据结构中常用的一些经典算法,用java编写,可直接复制运行。主要有:快排、求素数、基数排序、二分法查找、直接插入排序