转载

【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 }

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