題目鏈接
給定一個 n 個元素有序的（升序）整型數(shù)組 nums 和一個目標(biāo)值 target ，寫一個函數(shù)搜索 nums 中的 target卤妒，如果目標(biāo)值存在返回下標(biāo)甥绿，否則返回 -1字币。

示例 1:

輸入: nums = [-1,0,3,5,9,12], target = 9
輸出: 4
解釋: 9 出現(xiàn)在 nums 中并且下標(biāo)為 4
示例 2:

輸入: nums = [-1,0,3,5,9,12], target = 2
輸出: -1
解釋: 2 不存在 nums 中因此返回 -1

提示：

你可以假設(shè) nums 中的所有元素是不重復(fù)的。
n 將在 [1, 10000]之間共缕。
nums 的每個元素都將在 [-9999, 9999]之間洗出。

其實二分查找的思想比較容易理解，但是問題就在于搜索區(qū)間的開閉骄呼。如果不能明白每次搜索區(qū)間的首尾的開閉情況就會出現(xiàn)不能正確查詢出結(jié)果的問題共苛。下面兩個解法都能通過。

// 解法一
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int begin = 0, end = nums.size() ;

         while( begin < end ){
            int middle = (begin + end ) / 2;
        // 奇偶之分蜓萄，導(dǎo)致中間位置有偏差
            if(nums[middle] == target){
                return middle;
            }else if( nums[middle] > target){
                end = middle;
            }else{
                begin = middle + 1;
            }

        }
        return -1;
        
    }
    
};

// 解法二
class Solution {
public:
    int search(vector<int>& nums, int target) {
        
        int left, right;
        left = 0, right = nums.size() - 1;
        
        while( left <= right ){
           int mid = (left + right) / 2;

            if( nums[mid] > target ) right = mid-1;
            else if( nums[mid] < target) left = mid+1;
            else 
                return mid;
            
        }
        return -1;
        
    }
};

對于解法一：

我們將搜索區(qū)間定在了[ 0, nums.size() )隅茎， 顯然我們在程序中是不能夠訪問 nums[ nums.size() ] 這個元素的，因為這樣會導(dǎo)致邊界溢出嫉沽。在這個搜索區(qū)間下辟犀，我們的 middle = (left + right ) / 2 是正好指向整個搜索區(qū)間的中間元素的（元素個數(shù)為奇數(shù)個時正好指向中間位置，偶數(shù)個時則位于中間偏右位置）绸硕。

為了保持搜索區(qū)間的狀態(tài)一致性堂竟，我們在后續(xù)進行二分的時候?qū)?yīng)的區(qū)間也應(yīng)當(dāng)都是左開右閉的搜索狀態(tài)，這里具體下來就是：對于第一次遍歷的右頂點是屬于越界情況玻佩，后續(xù)的搜索過程中出嘹，右頂點都是屬于已遍歷過無需再次遍歷的狀態(tài)。所以每次的二分區(qū)間為 [left, middle), [middle +1, right)咬崔。

假設(shè)當(dāng)搜索區(qū)間中不存在目標(biāo)元素時税稼，搜索區(qū)間不斷向兩端收縮，最終到達 left == left或者 right == right 此時的搜索區(qū)間都是[left, left), [right, right) 的 狀態(tài)垮斯，實際上這樣的搜索區(qū)間都是空的郎仆，不可搜索的區(qū)間，因此這作為程序的終止條件兜蠕。

同理對于解法二：

這個解法是將整個搜索區(qū)間定在了[0, nums.size() -1], 這樣一來我們需要對整個搜索區(qū)間進行遍歷扰肌，在這個搜索區(qū)間下，我們的 middle = (left + right ) / 2 是正好指向整個搜索區(qū)間的中間元素的（元素個數(shù)為奇數(shù)個時正好指向中間位置熊杨，偶數(shù)個時則位于中間偏左位置）

同上思路曙旭，我們進行二分劃分搜索區(qū)間時，兩邊的頂點都應(yīng)該時保持左開右開的狀態(tài)晶府，即[left, middle-1], [middle+1, right ]桂躏。

同樣，在這個區(qū)間下最終的兩端狀態(tài)會變成[left, left],[right, right], 因為是都是開區(qū)間郊霎，所以這樣的區(qū)間還有一個元素需要遍歷沼头，因此我們程序的結(jié)束條件為 left > right 。

綜上， 在使用二分搜索進行查找元素時一定要保持最初的搜索空間和對應(yīng)的子搜索空間是保持一致的搜索狀態(tài)进倍，這樣才能正確對元素進行遍歷檢索土至。