1 題目

??經典二分搜索（Classical Binary Search）

lintcode：題號——457，難度——easy

2 描述

??在一個排序數組中找一個數，返回該數出現的任意位置，如果不存在，返回 -1。

??樣例 1：

輸入：nums = [1,2,2,4,5,5], target = 2
輸出：1 或者 2

??樣例 2：

輸入：nums = [1,2,2,4,5,5], target = 6
輸出：-1

3 思路

??對有序數組可以直接使用二分法，即拿著目標元素與中間位置的元素進行比較，判斷目標元素在當前位置的左區間還是右區間，再在目標區間內再次執行二分法，直到把子區間縮小到只有一個元素，即可找到或者不存在。

1. 找到中間位置的元素；
2. 與目標元素比較，確定目標元素所在的區間，縮小目標區間；
3. 重復以上操作，直到找到或者結束。

3.1 圖解

3.2 時間復雜度

??算法的時間復雜度為O(log n)。

3.3 空間復雜度

??算法的空間復雜度為O(1)。

4 模版

??算法雖然簡單，但是在邊界的處理上如果不注意的話很容易就產生“死循環”、“漏元素”、“越界”的情況，產生的原因有很多，例如：

1. 計算機的數據運算都是偏左的（給整數賦值“4.9”會被自動轉成“4”，不是四舍五入）
2. 比較大小的時候取“>”、“<”、">="、">="，會產生不同效果
3. 縮小區間時候取不取當前的中間元素，有可能導致死循環
4. 在數組的頭部和尾部要考慮越界的情況

??為解決上述問題，分享一個通用的二分法算法的模版，需要注意的點有四個，分別如下：

1. mid = start + (end - start) / 2
2. start + 1 < end
3. A[mid] ==, <, >
4. A[start] A[end] ? target

1. 取中點的時候使用start + (end - start) / 2，不使用(start + end) / 2，防止start和end很大的時候，start + end在整型范圍內越界；
2. 循環退出條件使用start + 1 < end，不使用start < end，防止死循環；
3. 循環內的判斷使用==、<和>單獨處理各個分支，不使用組合符號<=和>=，防止死循環；
4. 因為第二點的原因，所以循環退出后需要單獨判斷一次當前的start和end位置的元素。

5 源碼

??注意事項：

1. 最后是與target比較，不要寫錯成與start、end比較；
2. return的是index還是value要看清楚。

??C++版本：

/*經典二分搜索算法
* @param nums 有序數組
* @param target 目標元素的值
* @return 目標元素在有序數組中的位置（下標序號）
*/
int findPosition(vector<int> &nums, int target) {
    // write your code here
    if (nums.empty())
    {
        return -1;
    }
    
    int start = 0;
    int end = nums.size() - 1;
    int mid = 0;
    while (start + 1 < end) // 第二點：循環條件
    {
        mid = start + (end - start) / 2; // 第一點：取中點元素
        if (nums.at(mid) == target) // 第三點：單獨處理各個分支
        {
            return mid;
        }
        if (nums.at(mid) < target)
        {
            start = mid;
        }
        if (nums.at(mid) > target)
        {
            end = mid;
        }
    }
    
    if (nums.at(start) == target) // 第四點：處理循環退出后的start和end
    {
        return start;
    }
    
    if (nums.at(end) == target)
    {
        return end;
    }
    
    return -1;
}