1 題目

??尋找目標出現的初始位置（First Position of Target）

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

2 描述

??給定一個排序的整數數組（升序）和一個要查找的整數 target，用O(log n)的時間查找到target第一次出現的下標（從0開始），如果target不存在于數組中，返回-1。

??樣例：

輸入：數組 = [1,4,4,5,7,7,8,9,9,10], target = 4
輸出：1

3 思路

??從頭開始遍歷需要的時間復雜度是O(n)，要求在O(log n)的時間內完成，可以用二分法解決。

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

??與之前的經典二分搜索^[1]大致相同，可以套用經典二分搜索的模版，需要注意的差異如下：

1. 循環中與目標元素的比較在“>”和“==”時候的處理，都是拋掉右邊的部分；
2. 跳出循環之后，對剩下的兩個元素的檢查順序是從左到右。

3.2 圖解

3.2 時間復雜度

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

3.3 空間復雜度

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

4 源碼

??C++：

/**
* @param nums: 有序數組
* @param target: 目標元素的值
* @return: 目標元素在有序數組中的初始位置（下標序號）
*/
int binarySearch(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) // 大于和等于的情況處理方式相同
        {
            end = mid;
        }
        else
        {
            start = mid;
        }
    }
    
    if (nums.at(start) == target) // 先判斷左邊的是否是目標元素
    {
        return start;
    }
    if (nums.at(end) == target)
    {
        return end;
    }
    
    return -1;
}

5 相同類型問題

??題目：

尋找目標出現的最后位置（Last Position of Target）
lintcode：題號——458，難度——easy

??C++版本：

/**
* @param nums: 有序數組
* @param target: 目標元素的值
* @return: 目標元素在有序數組中的最后位置（下標序號）
*/
int lastPosition(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)
        {
            start = mid;
        }
        else
        {
            end = mid;
        }
    }
    
    if (nums.at(end) == target)
    {
        return end;
    }
    
    if (nums.at(start) == target)
    {
        return start;
    }
    
    return -1;
}