Fork me on GitHub

java算法(二) 二分查找

java算法二分查找

理解二分查找:

二分查找在刚开始学习java的时候会有一个例子,就是,我们写个猜数字的游戏,没有什么人是从1猜到100吧,如果你这么玩,那也没毛病,我会给你数字加到1个亿,哈哈!大家基本上都是从中间开始猜数字,如果大了,那就缩小范围,就是这个样子来的,这个就是二分查找的一个思想,但是,这个数组必须是有序的,要不然没有办法去排序的。

官方解读:

二分查找又成折半查找,一种效率较高的查找方法,折半查找算法的思想就是将元素值小于该中点元素,查询过程中采用跳跃方式查找,即以有序列的中点位置为比较对象,如果需要的元素值小于该中点元素,则将待查序列缩小为左半部分,否则右半部分,所以,这就要求先决条件为元素必须有序。

优缺点:

折半查找优点,次数少,速度快,平均性能好,缺点,要求待查表为有序表,而且插入删除困难,因此,适用与不经常变动的有序列表。
二分查找的步骤描述:
1、首先确定整个查找区间的中间位置 mid = (left + right) /2
2、用待查关键字值与中间位置的关键字进行比较;
如果相等,查询成功
如果大于,在右半个区域进行半折查询
如果小于,在左半个区域进行半折查询

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
* 二分查找
* Created by huxudong on 2017/9/16.
* @author huxudong
*/
public class Test2 {
public static void main(String[] args){
int[] srcArray= new int[]{1,3,5,7,8,9,10,20,30,40,50,60,70,80,90,103};
System.out.print(binarySearch(srcArray,0,srcArray.length-1,80));
}
/**
* 二分查找,递归实现
* @param srcArray
* @param start
* @param end
* @param key
* @return
*/
public static int binarySearch(int[] srcArray,int start, int end, int key){
int mid = (end -start)/2+start;
if(srcArray[mid] == key){
return mid;
}
if(start>=end){
return -1;
}else if (key > srcArray[mid]){
return binarySearch(srcArray,mid+1,end,key);
}else if (key < srcArray[mid]){
return binarySearch(srcArray,start,mid-1,key);
}
return -1;
}
}