package searching;
/*** 折半查找法的扩展应用* 面试题：* 给定一个有序数组，如果往该数组中存储一个元素，* 并保证这个数字还是有序的，那么该元素的存储的下标如何获取*/
public class MyBinSearch {public static void main(String[] args) {// TODO Auto-generated method stubint[] a={3,5,10,13,19,23,28,30,45,60,84,90,94,100};System.out.println(binSearch(a,94));System.out.println(InsertToArray(a,93));//结果应该是12System.out.println(InsertToArray(a,7));//结果应该是2System.out.println(InsertToArray(a,0));//结果应该是0}
//二分查找法插入元素，并保持原顺序不变
private static int InsertToArray(int[] a, int key) {int min=0,max=a.length-1;int mid=0;while(min<=max){mid=(max+min)/2;if (key>a[mid]) {min=mid+1;}else if (key<a[mid]) {max=mid-1;}else {return mid;}}return min;}private static int binSearch(int[] a, int key) {// TODO Auto-generated method stubint mid=a.length/2;if (a[mid]==key) {return mid;}int min=0;int max=a.length-1;while(min<=max){mid=min+(max-min)/2;if (key>a[mid]) {min=mid+1;}else if (key<a[mid]) {max=mid-1;}else {return mid;}}return -1;}}
