二分查找又称折半查找,它是一种效率较高的查找方法。
折半查找的算法思想是将数列按有序化(递增或递减)排列,查找过程中采用跳跃式方式查找,即先以有序数列的中点位置为比较对象,如果要找的元素值小于该中点元素,则将待查序列缩小为左半部分,否则为右半部分。通过一次比较,将查找区间缩小一半。 折半查找是一种高效的查找方法。它可以明显减少比较次数,提高查找效率。但是,折半查找的先决条件是查找表中的数据元素必须有序。
折半查找法的优点是比较次数少,查找速度快,平均性能好;其缺点是要求待查表为有序表,且插入删除困难。因此,折半查找方法适用于不经常变动而查找频繁的有序列表。
算法步骤描述
① 首先确定整个查找区间的中间位置 mid = ( low + high )/ 2
② 用待查关键字值与中间位置的关键字值进行比较;
若相等,则查找成功
若大于,则在后(右)半个区域继续进行折半查找
若小于,则在前(左)半个区域继续进行折半查找
③ 对确定的缩小区域再按折半公式,重复上述步骤。
最后,得到结果:要么查找成功, 要么查找失败。折半查找的存储结构采用一维数组存放。
public class Test{
public static < T extends Comparable < ? super T>> int binarySearch(T [] array,T key){
int low = 0;
int high = array.length-1;
while(low <= high){
int mid = (low + high)/2;
if(array[mid].compareTo(key)< 0){
low = mid + 1;
}else if(array[mid].compareTo(key)>0){
high = mid - 1;
}else{
return mid;
}
}
return -1;
}
public static void main(String args[]){
Integer a[]={1,2,3,4,5,6,7,8,9};
int k=binarySearch(a,7);
System.out.println("k="+k);
}
}
分享到:
相关推荐
数据结构八大算法,详细介绍了算法的如何实现,以及编码过程,有简单到复杂,由浅入深,看看会有很大收获。
折半(二分)查找算法C语言源程序,首先借助于快速排序算法对数组进行从小到大的排序,然后折半进行查找,直到找到相应数字为止。
在数组x中查找数字a,其中x是一个元素各异并按升序排列的一维数组.若找到a,则返回a在x中的位置,若a不在x中则返回“找不到”.
所谓的二分查找,指的是将待查的数据序列而分化,然后对比中间中间值和要查找值,判断结果,相等则找到,小于则在左边的子序列找,大于则在右边的子序列找
折半查找算法适合用于有序的数字列表,无序的数字列表适合顺序查找。 折半查找的实现步骤如下: 1. 假设表中的元素是按升序排列,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功;否则利用...
分别用递归和非递归方法实现二分查找算法 的完整程序,indexof()返回的是循环实现的二分法查找,getindex()实现的是递归算法实现的二分法查找。
C#实现 二分查找 折半查找 visual studio 2012开发环境 具有图形化界面
顺序查找、二分查找、插值查找、动态查找(数组实现、链表实现)
折半查找(又称二分查找)是一种高效的查找算法,适用于已排序的数组或列表。其基本思想是将待查找的元素与数组中间元素进行比较,如果相等则返回该元素的下标;如果待查找元素小于中间元素,则在数组左半部分继续...
C++数据结构折半查找法二分查找法,算法设计新颖,有利于数据结构初学者的学习!
用C语言开发的递归和非递归二分查找算法,具体内容详见代码
数据结构中简单的二分查找(折半查找)流程图实例
编写Search_Bin函数,实现在一个递增有序数组ST中采用折半查找法确定元素位置的算法. 输入格式 第一行:元素个数n 第二行:依次输入n个元素的值(有序) 第三行:输入要查找的关键字key的值 输出格式 输出分...
主要介绍了PHP折半(二分)查找算法,结合实例形式较为详细的分析了php折半(二分)查找算法的概念、原理、实现与使用方法,并附带了一个php折半(二分)查找算法类供大家参考,需要的朋友可以参考下
主要介绍了C++二分查找(折半查找)算法,结合实例形式详细分析了二分查找算法的原理、思想、实现方法与相关操作技巧,需要的朋友可以参考下
本文实例讲述了PHP有序表查找之二分查找(折半查找)算法。分享给大家供大家参考,具体如下: 简介: 二分查找技术,又称为折半查找。...//二分搜索(折半查找)算法(前提是数组必须是有序数组) 时间复杂度是 O(l
二分查找,也称为折半查找,是一种在有序数据集中查找特定元素的算法。它的高效性使得二分查找在多种应用场景中成为首选的搜索算法。下面我们将从原理、应用、性能分析及扩展变种等方面进行详细探讨。 二分查找的...
本文实例讲述了PHP实现的折半查找算法。分享给大家供大家参考,具体如下: 定义:折半查找技术,也就是二分查找。它的前提是线性表中的记录必须是关键码有序(通常从大到小有序),线性表必须采用顺序存储。 折半...
顺序查找表 二分查找表 折半查找表 二叉排序树 C#源代码 注意二叉排序树只实现了查找和插入算法,使用Visual Studio 2008开发