顺序查找与二分（折半）查找及其相关优化
>==================================================<
import java.util.Arrays; import java.util.Scanner; public class Search { public static final int[] A = {8,7,4,5,11,1,3,2,6,9,10,12}; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int key = sc.nextInt(); Arrays.sort(A); System.out.println(Search21(A,key)); } /** * 顺序查找 */ public static int Search1(int[] A,int key){ for(int i=0;i<A.length;i++){ if(A[i] == key) return i; } return -1; } /** * 顺序查找的优化 */ public static int Search12(int[] A,int key){ int i = 0; while(A[i] != key){ i++; } return i+1; } /** * 折半查找 * 数组是有序的 * 时间复杂度是logn */ public static int Search2(int[] A,int key){ int mid,low,high; low = 0; high = A.length-1; while(low<high){ mid = (low + high) / 2; if(A[mid] == key) return mid; else if(A[mid] > key) high = mid-1; else low = mid + 1; } return -1; } /** * 折半查找的优化方案 * mid=(low+high)/2=low+(high-low)/2 * 同理如果是三分查找则mid=（low+high）/3显然是错的。正确的应是mid=low+(high-low)/3 * 如何再改进呢？我们怎么才能知道查找一个数我们几分查找才是合适的（显然有时候二分并不是最好的） * mid=low+[(key-a[low])/(a[high]-a[low])]*(high-low) * 这其实就是插值查找了 */ public static int Search21(int[] A,int key){ int mid,low,high; low = 0; high = A.length-1; while(low<high){ mid = low + (key-A[low])/(A[high]-A[low]) * (high-low); if(A[mid] == key) return mid; else if(A[mid] > key) high = mid-1; else low = mid + 1; } return -1; } }
