JAVA实现二分查找

二分查找又称折半查找、二叉查找，它是一种效率较高的查找方法。

前提

给定一已排好序的n个元素a[0 : n-1]，现要在这n个元素中找出一特定元素x。

算法思想

首先，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。

 1 package com.example.test;
 2 
 3 public class BinarySearch {
 4 
 5     /***
 6      * 
 7      * @param a 已排好序的数组
 8      * @param dst 需要查找的目标值
 9      * @return 查找到目标值返回目标值在数组中的位置，没有超重到目标值返回-1
10      */
11     public int binarySearch(int[] a, int dst) {
12         
13         int flag = 0;
14         //先判断数组是顺序还是倒序
15         if (a[0] > a[a.length - 1]) {
16             System.out.println("array is reverse order");
17             flag = 1;  //数组为倒序
18         }
19         
20         int mid = -1;
21         int low = 0;
22         int high = a.length - 1;
23         if (0 == flag) {
24             while (low <= high) {
25                 mid = low + (high-low)/2; //此处不用(low + high)/2是防止low + high值溢出
26                 if (a[mid] == dst) {
27                     printSearchResult(a,dst,mid);
28                     return mid;
29                 } else if (dst < a[mid]) {
30                     high = mid - 1;
31                 } else {
32                     low = mid + 1;
33                 }
34             }
35         } else {
36             while (low <= high) {
37                 mid = low + (high-low)/2; //此处不用(low + high)/2是防止low + high值溢出
38                 if (a[mid] == dst) {
39                     printSearchResult(a,dst,mid);
40                     return mid;
41                 } else if (dst < a[mid]) {
42                     low = mid + 1;
43                 } else {
44                     high = mid - 1;
45                 }
46             }
47         }
48         
49         
50         System.out.println("not find the num " + dst + " in the array");
51         return -1;
52         
53     }
54     
55     /***
56      * 打印查找结果
57      * @param a 数组
58      * @param dst 查找的目标值
59      * @param position 目标值在数组中的位置
60      */
61     private void printSearchResult(int[] a,int dst, int position) {
62         String tmp = "find the num " + dst + " in the array {";
63         for (int i = 0; i < a.length - 2; i++) {
64             tmp += a[i] + ",";
65         }
66         tmp += a[a.length - 1] + "}, position is " + position;
67         System.out.println(tmp);
68     }
69     
70     public static void main(String[] args) {
71         int a[] = {1,3,5,7,8,9,10,12,15,17};
72         BinarySearch binarySearch = new BinarySearch();
73         binarySearch.binarySearch(a,17);
74         binarySearch.binarySearch(a, 8);
75         int b[] = {17,13,11,9,7,6,4,2,1};
76         binarySearch.binarySearch(b,17);
77         binarySearch.binarySearch(b, 4);
78         binarySearch.binarySearch(b, 1);
79     }
80     
81 }