条件是数组中可能出现重复的数字,很容易就会想到折半查找,但是对于重复元素怎么处理?
解决方法一:最先想到的就是二分查找找到待查找的数后,若存在相同的数,继续向左查找,直到找到第一个数为止。但是这样最坏的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
网友评论