【Java_Base】常用查找算法：順序查找、二分查找

順序查找

從第一個元素開始順序比較查找。

二分查找

二分查找前提條件： 已排序的數組中查找

二分查找的基本思想是: 首先確定該查找區間的中間點位置： int mid = (low+upper) / 2;

然后將待查找的值與中間點位置的值比較：

若相等，則查找成功并返回此位置。

若中間點位置值大于待查值，則新的查找區間是中間點位置的左邊區域。

若中間點位置值小于待查值，則新的查找區間是中間點位置的右邊區域。

下一次查找是針對新的查找區間進行的。

 1 public class Search{
 2     public static void main(String [] args){
 3         int[] array={13,4,56,7,88,7,78,66,34,56};
 4         System.out.println("待查找的數組序列為：");
 5         for(int arr:array){
 6             System.out.print(arr+" ");
 7         }
 8         //順序查找
 9         System.out.println("\n"+"順序查找66的下標為："+"\n"+sequentialSearch(array,66));
10         //排序數組
11         System.out.println("排序后的數組序列為：");
12         Sort(array);        
13         //二分法查找
14         System.out.println("\n"+"二分法查找88的下標為："+"\n"+binarySearch(array,88));
15         
16     }
17     //順序查找
18     public static int sequentialSearch(int[] a,int num){
19         int n=a.length;
20         for(int i=0;i<n;i++){
21             if(a[i]==num){
22                 return i;
23             }
24         }
25         return -1;
26     }
27     //二分查找
28     public static int binarySearch(int [] a,int num){
29         //起點
30         int low=0;
31         //終點
32         int upper=a.length-1;
33         //避免出現下標越界異常
34         while(low<=upper){
35             //中間點
36             int mid=(low+upper)/2;
37             //中間點的值小于要查找的值,更改查找的起點為中間點位置后一位
38             if(a[mid]<num){
39                 low=mid+1;
40             }
41             //中間點的值大于要查找的值,更改查找的終點為中間點位置前一位
42             else if(a[mid]>num){
43                 upper=mid-1;
44             }
45             else{
46                 return mid;
47             }
48             
49         }
50         return -1;
51     }
52     
53     
54     //排序數組
55     public static void Sort(int[] a){
56         int n=a.length;
57         //i是比較的次數，共比較n-1次
58         for(int i=1;i<n;i++){
59             //j是進行比較的第一個元素的下標
60             for(int j=0;j<n-1;j++){
61                 if(a[j]>a[j+1]){
62                     int temp=a[j+1];
63                     a[j+1]=a[j];
64                     a[j]=temp;
65                 }
66             }
67         }
68         //遍歷已排序數組
69         for(int k=0;k<n;k++){
70             System.out.print(a[k]+" ");
71         }
72     }
73     
74 }