二分查找算法一般要求數(shù)組是有序的，應用過程中必須要設置一個基準值，用數(shù)組中間部位的值與基準值比較進而更新查找區(qū)間。

二分查找算法的基本框架：

public int searchNum(int[]nums,int target){
    int l=0;
    int r=nums.length-1;
    while(l<=r){
        int mid=(l+r)/2;
        if(nums[mid]==target){
            return mid;
        }else if(target<nums[mid]){
            r=mid-1;
        }else{
            l=mid+1;
        }
    }
    return -1;//表示沒有找到該數(shù)字
}

二分查找算法的邊界問題：

情況1：在區(qū)間[left,right)內使用二分查找算法尋找答案，注意這里的區(qū)間是左閉右開的。在更新right時，只能是right=mid,其中mid=left+(right-left)/2。

那么為什么不能是right=mid-1呢？理由很簡單，假設將right更新為mid-1，則查找區(qū)間變成了[left,mid-1),因為右邊是開區(qū)間，所以mid-1是查找不到的，而更新right之前只能說明索引mid處不是我們要查找的答案，并不能說明mid-1處也不是正確答案，mid-1處仍然是要考慮的?？傊?，開區(qū)間的一側一定不能縮小區(qū)間。而left要更新為mid+1,才能保證區(qū)間里的每個元素都能被訪問到。

情況2：在[left,right]內使用二分查找尋找答案，這里是左閉右閉的區(qū)間。根據(jù)情況1的分析可知更新區(qū)間應為：left=mid+1,right=mid-1,可以保證區(qū)間里的每個元素都能被訪問到。

經(jīng)過上述分析，可以說運用二分查找算法的總體流程應分為3個步驟：

1、確定基準值，將這一步驟單獨拿出來主要是為了針對二分查找算法的一些變體。

2、確定查找區(qū)間，及區(qū)間的更新方式。

3、調試結果。

1、旋轉數(shù)組中的最小數(shù)字

JZ6題目描述：

把一個數(shù)組最開始的若干個元素搬到數(shù)組的末尾，我們稱之為數(shù)組的旋轉。輸入一個非遞減排序的數(shù)組的一個旋轉，輸出旋轉數(shù)組的最小元素。
NOTE：給出的所有元素都大于0，若數(shù)組大小為0，請返回0。

示例：

輸入
[3,4,5,1,2]
返回值
1

解答：

本題考查二分查找算法的靈活運用，有序數(shù)組旋轉后會變成兩部分有序的數(shù)組。

本題的基準值設置為查找區(qū)間最右邊的值，那能不能將左左邊的值設置為基準值吶，答案是不能的，理由如下，假如有一個數(shù)組為[1,2,3,4,5]，基準值target=1,中間值mid=3,此時mid是大于基準值的，這種情況下答案1在mid的左邊?，F(xiàn)有另一數(shù)組[3,4,5,1,2],基準值target=3,中間值mid=5,mid仍然是大于基準值的，而這種情況下答案1卻在mid的右邊。意思是將基準值設置在最左邊，對于同樣中間值大于基準值的情況，會出現(xiàn)兩種情況，有時候答案在左部分，有時候卻在右部分，因此無法正確更新查找區(qū)間。

public int minNumberInRotateArray(int [] array){
        //一定要選擇最右邊的元素作為基準值
        int left=0;
        int right=array.length-1;
        if(right<0)return 0;
        //int target=array[right];
        while(left<right){
            int mid=left+(right-left)/2;
            if(array[mid]>array[right]){
                left=mid+1;
            }
            else if(array[mid]<array[right]){
                right=mid;
            }
            else{
                //如果是 1 0 1 1 1， arr[mid] =    target = 1, 顯然答案在左邊
                //如果是 1 1 1 0 1, arr[mid] = target = 1, 顯然答案在右邊
                //所以這種情況，不能確定答案在左邊還是右邊，那么就讓last = last - 1;慢慢縮少區(qū)間，同時也不會錯過答案。
                 right--;
            }
        }
        return array[right];
    }

2、二維數(shù)組中的查找

JZ1題目描述：

在一個二維數(shù)組中（每個一維數(shù)組的長度相同），每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。請完成一個函數(shù)，輸入這樣的一個二維數(shù)組和一個整數(shù)，判斷數(shù)組中是否含有該整數(shù)。

輸入
7,[[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]]
返回值
true

解答：

該二維數(shù)組每一行和每一列中的元素都是遞增排列的，因此可以使用二分查找算法的思想來查找元素。運用二分查找算法的時候，選定的中間值mid必須滿足整體有序的，即在上述示例中可以選擇array[0] [3]作為中間值mid， 該mid值所在行是遞增的，所在列也是遞增的。

public class Solution {
    //對二維有序數(shù)組進行二分查找
    public boolean Find(int target, int [][] array) {
        int row=array.length;
        if(row==0) return false;
        int col=array[0].length;
        int i=0;int j=col-1;
        while(i<row&&j>=0){
            if(target>array[i][j]){
                i++;
            }
            else if(target<array[i][j]){
                j--;
            }
            else{
                return true;
            }
        }
        return false;
    }
}

3、查找左右邊界

假設有一個有序數(shù)組{1,2,2,2,3}，這個時候讓你查找target=2的邊界，便可以使用二分查找算法來分別查找有序數(shù)組的左右邊界。

查找左邊界：

public int findLeftBound(int[] nums,int target){
    int left=0;
    int right=nums.length-1;
    while(left<right){//注意：區(qū)間對應
        int mid=left+(right-left)/2;
        if(target<=nums[mid]){
            right=mid;
        }
        else{
            left=mid+1;
        }
    }
    return left;
}

查找右邊界：

public int findRightBound(int[] nums,int target){
    int left=0;
    int right=nums.length-1;
    while(left<right){注意：區(qū)間對應
        int mid=left+(right-left)/2;
        if(target<nums[mid]){
            right=mid-1;
        }
        else{
            left=mid;
        }
    }
    return right;
}