最近打算换工作，频繁面试，现把面试题及其解答记录下来，方便学习。
问题：有一个升序排列无重复数字的数据，以及一个数字，利用二分法查找数字在数组中的位置，找到则返回其位置号，没找到返回-1.
解答：
通过两种方式实现：第一种方式为递归实现，需要传递数组的头和尾的位置。
public class MidFind {
/**
*
* @param arr
* @param key
* @param startNum 数组位置号，为数组下标+1
* @param endNum 数组位置号，为数组下标+1
* @return
*/
public static int getLocation(int[] arr,int key,int startNum,int endNum) {
if (arr==null) return -1;
int middleNum=(startNum+endNum)/2;
System.out.println("中间值："+middleNum);
if (startNum<endNum) {
if (key==arr[middleNum]) {
return middleNum+1;
} else if (key<arr[middleNum]) {
return getLocation(arr,key,startNum,middleNum);
} else {
return getLocation(arr,key,middleNum,endNum);
}
} else if (startNum==endNum) {
return startNum;
} else {
return -1;
}
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] arr={1,3,4,5,6,7,11,46,255,743,888};
int temp=getLocation(arr,11,1,11);
System.out.println(temp);
}
}
第二种实现方式为非递归实现，则利用循环：
public class MidFind2 {
public static int getLocation(int[] arr,int key) {
if (arr==null) return -1;
int middleNum=arr.length/2;
if (key==arr[middleNum]) {
return middleNum+1;
}
int startNum=0; //数组下标
int endNum=arr.length-1; //数组下标
while (startNum<=endNum) {
middleNum=(startNum+endNum)/2;
if (key<arr[middleNum]) {
endNum=middleNum;
} else if (key>arr[middleNum]) {
startNum=middleNum;
} else {
return middleNum+1;
}
}
return -1;
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] arr={1,3,4,5,6,7,11,46,255,743,888};
int temp=getLocation(arr,5);
System.out.println(temp);
}
}