package com.myway.study;
/**
* 二分查找算法是在有序数组中用到的较为频繁的一种算法,在未接触二分查找算法时,最通用的一种做法是,对数组进行遍历,跟每个元素进行比较,其时间为O(n).但二分查找算法则更优,因为其查找时间为O(lgn),譬如数组{1, 2, 3, 4, 5, 6, 7, 8, 9},查找元素6,用二分查找的算法执行的话,其顺序为:
* 1.第一步查找中间元素,即5,由于5<6,则6必然在5之后的数组元素中,那么就在{6, 7, 8, 9}中查找,
* 2.寻找{6, 7, 8, 9}的中位数,为7,7>6,则6应该在7左边的数组元素中,那么只剩下6,即找到了。
* 二分查找算法就是不断将数组进行对半分割,每次拿中间元素和goal进行比较
* User: zhangyong
* Date: 14-5-14
* Time: 下午10:06
* To change this template use File | Settings | File Templates.
* 二分查找的基本思想是将n个元素分成大致相等的两部分,去a[n/2]与x做比较,如果x=a[n/2],则找到x,算法中止;如果x<a[n/2],则只要在数组a的左半部分继续搜索x,如果x>a[n/2],则只要在数组a的右半部搜索x.
时间复杂度无非就是while循环的次数!
总共有n个元素,
渐渐跟下去就是n,n/2,n/4,....n/2^k,其中k就是循环的次数
由于你n/2^k取整后>=1
即令n/2^k=1
可得k=log2n,(是以2为底,n的对数)
所以时间复杂度可以表示O()=O(logn)
*/
public class BinarySearch {
public int sort(int[] arr, int searchNum) {
int length = arr.length;
int low = 0;
int high = length - 1;
while (low <= high) {
int middle = (low + high) / 2;
int middleValue = arr[middle];
if (middleValue == searchNum) {
return middle;
} else if (middleValue > searchNum) {
high = middle;
} else {
low = middle;
}
}
return -1;
}
public static void main(String[] args) {
int[] arr = {1, 2, 3, 5, 6, 7, 8};
System.out.println(new BinarySearch().sort(arr, 7));
}
}
分享到:
相关推荐
用java实现二分查找法BianrySearch 用java实现二分查找法BianrySearch 用java实现二分查找法BianrySearch
C++ 二分查找法
用java二分查找法实现日期搜索 用java二分查找法实现日期搜索 用java二分查找法实现日期搜索
该程序是我写的博客“一起talk C栗子吧(第二十五回:C语言实例-二分查找)”的配套程序,共享给大家使用
在已排序好的数组T中运用二分查找的方法查找目标数的位置。 根据实验要求和伪码信息,用二分查找的方法在输入的排序好的数组T中查找目标数的位置。若目标数在数组中输出下标位置,不在则输出零。
java 二分查找法的实现方法 java 二分查找法的实现方法
假设有一个人要我们猜0-99之间的一个数,那么最好的方法就是从0-99的中间数49开始猜。 如果要猜的数小于49,就猜24(0-48的中间数);如果要猜的数大于49,就猜74(50-99的中间数)。...二分查找的工作方法就是如此。
二分查找法 课件 描述了二分查找的前提条件 和基本思想,算法过程
matlab实现二分查找,里面具有详尽的代码和注释,保证一看就懂
编写程序对数据序列采用二分查找法和顺序查找法查找元素的下标,要求使用类模板实现(其中二分法查找算法要求用递归实现,给定数据序列有序)。
二分查找法的优点:查找速度快 1024个长度的表最长只需10次查表就能得出结果 在用NTC测试温度的方案中,NTC的温度表的长度一般是100-200 有些达到400-500的长度 在这种情况下如果用逐个查表比较的方法来查温度 会...
二分查找法进阶.zip
二分查找法.pptx
项目使用过的二分查找法源码
c++ 二分查找法,test ok
二分查找法简要示例代码,下载后使用PYTHON运行。如此这般、
Python 算法 19二分查找法.mp4
数据结构之二分查找法,供大家学习数据结构时参考。作者是一名大学生,如有错误,敬请原谅!