二分查找算法(Java)

今天在公司闲着蛋疼，网上瞎逛，偶然在InfoQ网站上看到一篇文章《计算机科学中最重要的32个算法》，原文地址：http://www.infoq.com/cn/news/2012/08/32-most-important-algorithms?utm_source=infoq&utm_medium=popular_links_homepage，里面就有二分查找算法，于是乎动手实现此算法，看自己是否掌握了，倒腾半天才写出来，汗颜哪。写下此文，一来回顾一下二分查找算法，而来警醒自己。

一、概念

二分查找算法也称折半查找，是一种在有序数组中查找某一特定元素的搜索算法。

二、算法思想

搜素过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜素过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。

三、优缺点

二分查找算法的优点是比较次数少，查找速度快，平均性能好;其缺点是要求待查表为有序表，且插入删除困难。因此，二分查找算法适用于不经常变动而查找频繁的有序列表。

四、复杂度分析

(1) 时间复杂度

二分查找每次把搜索区域减少一半，时间复杂度为。（n代表集合中元素的个数）

(2)空间复杂度

。

五、代码实现

(1) 迭代实现

01	publicstaticintbinarySearch(int[] arr,inttarget) {

02	intbot =1;

03	inttop = arr.length;

04	while(bot <= top) {

05

// 防止溢出

06	intmid = (bot + top) >>>1;

07	if(target > arr[mid]) {

08	bot = mid +1;

09	}elseif(target < arr[mid]) {

10	top = mid -1;

11

}else{

12	returnmid;

13

}

14

}

15

return-1;

16

}

(2)递归实现

01

/**

02	* 递归实现二分查找算法

03

*

04	* @param arr

05	* @param fromIndex

06	* @param toIndex

07	* @param key

08

* @return

09

*/

10	publicstaticintbinarySearch(int[] arr,intfromIndex,inttoIndex,inttarget) {

11	while(fromIndex <= toIndex) {

12

// 防止溢出

13	intmid = (fromIndex + toIndex) >>>1;

14	if(arr[mid] < target) {

15	returnbinarySearch(arr, mid +1, toIndex, target);

16	}elseif(arr[mid] > target) {

17	returnbinarySearch(arr, fromIndex, mid -1, target);

18

}else{

19	returnmid;

20

}

21

}

22

return-1;

23

}

总结：1、最开始在写代码的时候，没有考虑到溢出。

2、没想到用递归实现。