二分查找之Java實現

環境：Notpad ++ 6.0 + JDK 6.0.24

問題：用Java實現二分查找算法

算法剖析：

二分查找是在一個有序表(數據是按其值由小到大或由大到小依次存放的，這裡我們以值由小到大排列為例)中，每次都與中間的那個元素比較，若相等則查找成功；否則，調整查找范圍，若中間那個元素的值小於待查值，則在表的後一半中查找；若中間那個元素的值大於待查值，則在表的前一半中查找；如此循環，每次只與一半中的一個元素比較，可使查找效率大大提高。

代碼：

1. import java.util.*;
3. public class FindSearch{
5. public static void main(String [] args){
8. int a[] = {2, 4, 7, 18, 25, 34, 56, 68, 89};
9. System.out.println("打印原始數據：");
10. for (int i = 0; i < a.length; ++ i){
11. System.out.print(a[i] + " ");
12. }
13. System.out.println();
15. System.out.println("請輸入要查找的整數：");
16. Scanner scan = new Scanner(System.in);
17. int num = scan.nextInt();
18. int pos = 0;
19. pos = binaryFind(a, num);
20. if (-1 != pos)
21. System.out.println("所查整數在數組中的位置下標是：" + pos);
22. else
23. System.out.println("沒找到待查數據!");
24. }
26. public static int binaryFind(int a[],int num){
28. int low, mid, high;
30. low = 0;//low是第一個數組元素的下標
31. high = a.length - 1;//high是最後一個數組元素的下標
32. mid = (low + high) / 2;//mid是中間那個數組元素的下標
34. while (low <= high){
36. if (num == a[mid]){
37. return mid;
38. }else if (num > a[mid]){
39. low = mid + 1;//要找的數可能在數組的後半部分中
40. mid = (low + high) / 2;
41. }else{
42. high = mid - 1;//要找的數可能在數組的前半部分中
43. mid = (low + high) / 2;
44. }
45. }
48. //mid是數組元素下標，若為-1則表示不存在要查的元素
49. if (mid != ((low + high) / 2))
50. return mid;
51. else
52. return -1;
54. }
55. }

運行效果截圖：