Java针对数组的普通查找法和二分查找法

Java针对数组的普通查找法和二分查找法

1. package com.jadyer.sort;  
2.   
3. /** 
4.  * 数组查找方式 
5.  * @detail 这里演示了普通查找法和二分查找法 
6.  */  
7. public class ArraySearch {  
8.     public static void main(String[] args) {  
9.         int commonResult = commonSearch(new int[]{1,5,6,7,4,3,9,11,13,14,16,19,21}, 9);  
10.         int binaryResult = binarySearch(new int[]{1,3,4,6,7,8,9,12,15,17,18,20,22}, 8);  
11.         System.out.println("二分查找法: " + binaryResult);  
12.         System.out.println("普通查找法: " + commonResult);  
13.     }  
14.       
15.     /** 
16.      * 普通查找法 
17.      * @detail 该方式最好理解，同时效率也最低 
18.      */  
19.     public static int commonSearch(int[] array, int value){  
20.         for(int i=0; i<array.length; i++){  
21.             if(value == array[i]){  
22.                 return i; //返回该元素在数组中的下标   
23.             }  
24.         }  
25.         return -1; //不存在该元素则返回-1   
26.     }  
27.   
28.     /** 
29.      * 二分查找法 
30.      * @detail 要求数组有序，升序或降序均可 
31.      */  
32.     public static int binarySearch(int[] array, int value){  
33.         int low = 0; //最小元素值的下标   
34.         int high = array.length - 1; //最大元素值的下标   
35.         int middle; //中间元素的下标   
36.         while(low <= high){  
37.             middle = (low+high) / 2;  
38.             for(int i=0; i<array.length; i++){  
39.                 System.out.print(array[i]);  
40.                 if(i == middle){  
41.                     System.out.print("#"); //在元素后面用#号标识其为中间元素   
42.                 }  
43.                 System.out.print(" "); //各元素间用空格隔开   
44.             }  
45.             System.out.println();  
46.             if(value == array[middle]){  
47.                 return middle;  
48.             }  
49.             if(value < array[middle]){  
50.                 high = middle - 1; //右侧的不要了   
51.             }  
52.             if(value > array[middle]){  
53.                 low = middle + 1; //左侧的不要了   
54.             }  
55.         }  
56.         return -1; //不存在该元素则返回-1   
57.     }  
58. }