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

jopen 8年前

顺序查找

从第一个元素开始顺序比较查找。

二分查找

二分查找前提条件: 已排序的数组中查找

二分查找的基本思想是: 首先确定该查找区间的中间点位置: 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】常用查找算法:顺序查找、二分查找

来自: http://www.cnblogs.com/JayAnother/p/5083741.html