折半查找也叫二分法查找，即对数组二分取中间值和key比较key如果大于中间值，那么key一定在大的那一半，再对这一半进行二分，如此下去
它的特点是很快速高效率
缺点是要求数组是有序的

面试的时候会考到一种相关题型，即让你把一个数插入到一个有序的数组中，并且保证数组还是有序的。

下面是折半查找代码

1. /*
   
2. 折半查找
   
3. */
   
4. class ArrayTest02
   
5. {
   
6.         public static void main(String[] args)
   
7.         {
   
8.                 /*
   
9.                 int[] arr = {3,1,5,4,7,9};
   
10.                 int index = getIndex(arr,7);
    
11.                 System.out.println("index = "+index);
    
12.                 */
    
13.                 int[] arr = {2,4,7,9,11,35,56};
    
14.                 int index = halfSearch_2(arr,5);
    
15.                 System.out.println("index = "+index);
    
16.         }
    
17. 
    
18. 
    
19.         //折半查找:可以提高效率。
    
20.         //前提条件:该数组是有序的从大到小或者从小到大。
    
21.         public static int halfSearch(int[] arr, int key)
    
22.         {
    
23.                 int min,mid,max;
    
24.                 min = 0;
    
25.                 max = arr.length-1;
    
26.                 mid = (min+max)/2;
    
27. 
    
28.                 while(key!=arr[mid])
    
29.                 {
    
30.                         if (key>arr[mid])
    
31.                                 min = mid+1;
    
32.                         else if (key<arr[mid])
    
33.                                 max = mid-1;
    
34.                         if (max < min)
    
35.                                 return -1;
    
36.                         mid = (min + max)/2;
    
37.                 }
    
38.                 return mid;
    
39.         }
    
40. 
    
41. 
    
42.         //折半查找的第二种方式。
    
43.         public static int halfSearch_2(int[] arr, int key)
    
44.         {
    
45.                 int min,mid,max;
    
46.                 min = 0;
    
47.                 max = arr.length-1;
    
48. 
    
49.                 while (min <= max)
    
50.                 {
    
51.                         mid = (min + max)/2;
    
52. 
    
53.                         if(key>arr[mid])
    
54.                                 min = mid+1;
    
55.                         else if(key<arr[mid])
    
56.                                 max = mid-1;
    
57.                         else
    
58.                                 return mid;
    
59.                 }
    
60.                 return -1;
    
61.         }
    
62. 
    
63. 
    
64.         //定义一个遍历查找数组中任意元素的方法。
    
65.         //获取key第一次出现在数组中的位置。
    
66.         //如果返回值为-1，证明该key在数组中不存在。
    
67.         public static int getIndex(int[] arr, int key)
    
68.         {
    
69.                 for (int x=0; x<arr.length; x++)
    
70.                 {
    
71.                         if (key == arr[x])
    
72.                                 return x;
    
73.                 }
    
74.                 return -1;
    
75.         }
    
76. }
    

复制代码

值得学习ing!

写个快速查找算法试试