在有序数组中找到某个数

条件是数组中可能出现重复的数字，很容易就会想到折半查找，但是对于重复元素怎么处理？

解决方法一：最先想到的就是二分查找找到待查找的数后，若存在相同的数，继续向左查找，直到找到第一个数为止。但是这样最坏的time cost是o(n)。

怎么样可以达到最坏情况下也是o(logn）呢，想到了下面的方法

解决方法二：如果是最左边的数则是我们要找的；否则，right=mid-1继续查找

talk is cheap, show you my code

#include <iostream>

int find_first_num(const vector<int> v, int n)
{
    int res = -1;
    int left = 0;
    int right = v.size() - 1;
    while (left <= right)
    {
        int mid = (left + right) >> 1;
        if (v[mid] < n)
        {
            left = mid + 1;
        }
        else if (v[mid] > n)
        {
            right = mid - 1;
        }
        else
        {
            if (0 == mid || (mid > 0 && v[mid-1] != v[mid]))
            {
                res = mid;
                break;
            }
            else
            {
                right = mid - 1;
            }
        }
    }
    
    return res;
}

int main() {
    vector<int> v{1, 2, 3, 3, 6, 9};
    cout << find_first_num(v, 3);
    
    vector<int> v1{2, 2, 3, 3, 6, 9};
    cout << find_first_num(v, 2);
    
    vector<int> v2{2, 2, 2, 2, 2, 2};
    cout << find_first_num(v, 2);
}

运行结果

2
2
1