package cn.edu.ujn.demo;
 
public class BinarySearch {
 
/**
 * @param args
 */
public static void main(String[] args) {
int [] array = {1,2,3,4,4,7,12};
int len = array.length;
//System.out.println(binarySearchRecursion(array, 7, array[0], array[len-1]));
System.out.println(binarySearchRecursionNon(array, 7, array[0], array[len-1]));
}
/**
 * 二分查找(递归)
 * @param arry 递增数组
 * @param value 待查找数值
 * @param start 起始查找位置
 * @param end 末查找位置
 * @return
 */
private static int binarySearchRecursion(int arry[],int value,int start,int end)
{
    if(start > end)
        return -1;
 
    int mid=start + (end-start)/2;
    if(arry[mid] == value)
        return mid;
 
    else if(value < arry[mid])
    {
        end = mid - 1;
        return binarySearchRecursion(arry,value,start,end);
    }
    else
    {
        start = mid + 1;
        return binarySearchRecursion(arry,value,start,end);
    }
}
/**
 * 二分查找(非递归)
 * @param arry 递增数组
 * @param value 待查找数值
 * @param start 起始查找位置
 * @param end 末查找位置
 * @return
 */
private static int binarySearchRecursionNon(int arry[],int value,int start,int end)
{
while(start <= end){
    int mid=start + (end-start)/2;
    
    if(arry[mid] == value)
        return mid;
    
    else if(value < arry[mid])
    {
        end = mid - 1;
    }
    
    else
        start = mid + 1;
}
return -1;
}
}

/**
 * 在轮转后的有序数组上应用二分查找法
 * @param array
 * @param low
 * @param high
 * @param target
 * @return
 */
int searchInRotatedSortedArray(int array[], int low, int high, int target)
{
    while(low <= high)
    {
        int mid = (low + high) / 2;
        if (target < array[mid])
            if (array[mid] < array[high])	// the higher part is sorted
                high = mid - 1; // the target would only be in lower part
            else 	// the lower part is sorted
                if(target < array[low])	// the target is less than all elements in low part
                    low = mid + 1;
                else
                    high = mid - 1;
 
        else if(array[mid] < target)
            if (array[low] < array[mid])	// the lower part is sorted
                low = mid + 1;	// the target would only be in higher part
            else 	// the higher part is sorted
               if (array[high] < target)   // the target is larger than all elements in higher part
                    high = mid - 1;
                else
                    low = mid + 1;
        else 	// if(array[mid] == target)
            return mid;
    }
    return -1;
}