public class BinarySearchDemo {
/**
* 给定一个有序数组arr,再给定一个整数num,请在arr中找到num这个数出现的最左边的位置。
*/
public static int findNumFromArr(long[] arr,long num,int lo,int hi){
int res=-1;
if(arr==null||lo>hi)return res;
int mid = lo +(hi-lo)/2;
if(arr[mid]<num){
return findNumFromArr(arr, num,mid+1,hi);
}else if(arr[mid]>num){
return findNumFromArr(arr, num,lo,mid-1);
}else{
res = mid;
int res1=findNumFromArr(arr, num,lo,mid-1);
if(res1==-1){
return res;
}else{
return res1;
}
}
}
// [6,7,1,2,3,4,5]
// [4,5,6,1,2]
// [4,5,6,3,4]
/**
* 在有序循环数组中找到最小值
*/
public static int findMin(long[] arr,int lo,int hi){
int mid = lo +(hi -lo )/2;
if(lo==hi)return lo;
//最小值在最左边
if(arr[lo] < arr[hi]){
return lo;
}else {
if(arr[lo]>arr[mid]){
return findMin(arr,lo+1,mid);
}else{
if(arr[mid]>arr[hi]){
return findMin(arr,mid+1,hi);
}else{
return findMin(arr,mid,hi-1);
}
}
}
}
public static void main(String[] args) {
long[] arr = {4,4,5,5,4};
// System.out.println(findNumFromArr(arr, 7,0,arr.length-1));
System.out.println(findMin(arr,0,arr.length-1));
}
}
二分法查找
原文：http://blog.51cto.com/12336708/2106140
