有序数组二分查找的基本原理:因为数组是有序的,先找到中间位置的值,如果目标比这个值大,那么该目标必定在数组的右半部分,以此循环或者递归,一直找到这个数值为止。此算法的时间复杂度为O(logN),N为数组的长度
package algorithm.arrayfind;
public class SortedArrayBinarySearch {
public static void main(String[] args) {
int[] source=new int[]{1,3,5,7,9,12};
int key = 12;
System.out.println(binaryRecurSearch(source, key));;
System.out.println(binarySearchLoop(source, key));;
}
public static int binaryRecurSearch(int[] source, int key){
return binarySearchRecursive(source, key,0,source.length-1);
}
private static int binarySearchRecursive(int[] source, int key,int beginIndex,int endIndex){
int midIndex = (beginIndex+endIndex)/2;
if(key<source[beginIndex]||key>source[endIndex]||beginIndex>endIndex){
return -1;
}
System.out.println("=======");
if(key == source[midIndex]){
return midIndex;
}else if(key > source[midIndex]){
return binarySearchRecursive(source, key, midIndex+1, endIndex);
}else{
return binarySearchRecursive(source, key, beginIndex, midIndex-1);
}
}
public static int binarySearchLoop(int[] source, int key){
int beginIndex = 0;
int endIndex = source.length-1;
while(true){
System.out.println("=======");
if(key<source[beginIndex]||key>source[endIndex]||beginIndex>endIndex){
return -1;
}
int midIndex = (beginIndex+endIndex)/2;
if(key == source[midIndex]){
return midIndex;
}else if(key > source[midIndex]){
beginIndex = midIndex +1;
}else{
endIndex = midIndex -1;
}
}
}
}
分享到:
相关推荐
函数 实现一个整型有序数组的二分查找
Visual C++,有序数组的折半查找,和顺序查找法相比,其速度更快。
二分查找(Binary Search)是一种在有序数组中查找特定元素的算法。该算法的基本思想是先确定待查找区间的中间位置,然后将待查找元素与中间位置元素进行比较,根据比较结果缩小待查找区间的范围,直至找到目标元素...
JS实现二分查找查找有序数组中的数字,前端必会
给定一个单调递增的整数序列,问某个整数是否在序列中。输入样例: 5 1 3 4 7 11 3 3 6 9 输出样例: Yes No No
二分查找是一种高效的搜索算法,特别适用于有序数组。在这个教程中,我们将深入研究二分查找算法的工作原理,并提供一个Java示例来演示如何实现它。无论您是初学者还是有经验的Java开发者,通过学习这个算法,您将...
本文实例讲述了Python实现二维有序数组查找的方法。分享给大家供大家参考,具体如下: 题目:在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入...
二分查找
二分查找是一种在有序数组中查找某一特定元素的搜索算法。该算法的工作原理是,在每一次迭代中,算法都会比较数组中间的元素与目标值。如果目标值等于中间元素,则搜索过程结束;如果目标值小于中间元素,则算法会在...
编写Search_Bin函数,实现在一个递增有序数组ST中采用折半查找法确定元素位置的算法. Input 第一行:元素个数n 第二行:依次输入n个元素的值(有序) 第三行:输入要查找的关键字key的值 Output 输出分两种情形:...
《算法导论》(Introduction to Algorithms)原书第二版 Thomas H Cormen(科曼) Charles E Leiserson Ronald L Rivest Clifford Stein著 南京大学潘金贵 顾铁成 李成法 叶懋等译 机械工业出版社 2006 本书简称CLRS...
二分查找(Binary Search),也称折半查找,是一种效率较高的查找方法。它要求线性表必须采用顺序存储结构,且表中元素按关键字有序排列。二分查找充分利用了元素间的次序关系,采用分治策略,可在最坏的情况下用O...
很好的代码哟!增加,删除元素,二分查找元素
本篇文章主要介绍了详解Java数据结构和算法(有序数组和二分查找),具有一定的参考价值,感兴趣的小伙伴们可以参考一下
12、有序数组二分查找问题:这道题考查对有序数组二分查找算法的理解和使用。在这道题中,查找3的二分查找序列是5->2->3。 13、ConcurrentHashMap问题:这道题考查对Java并发编程的理解和使用。在这道题中,...
java二分查找开发技术实现代码,注意二分查找必须是有序数组
题目描述 把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的...而本题研究的对象是有序数组的旋转。菜鸡觉得这道题目颇为简单,只要遍历数组array,如果存在array[i] < array[0],那么array[i]一定就是
本文实例讲述了JavaScript使用二分查找算法在数组中查找数据的方法。分享给大家供大家参考。具体分析如下: 二分查找又称折半查找,优点是比较次数少,查找速度快,平均性能好;其缺点是要求待查表为有序表,且插入...
0702. 搜索长度未知的有序数组标签:二分查找难度:中等题目大意给定一个升序数组 nums,但是数组的大小是未知的,只能通过接口 reader.get(k)
例如,在一维数组[21,46,24,99,57,77,86]中,查找数据元素99,首先从第1个元素21开始进行比较,比较结果与要查找的数据不相等,接着与第2个元素46进行比较,以此类推,当进行到与第4个元素比较时,它们相等,...