第一个数字 =n 的 C++ 搜索算法

Question

我想要一个与二进制搜索类似的算法，其中我有一个数字 n，比方说 3，以及一个数组，如下所示：

array[10] = {1,2,3,3,3,3,3,3,3,4,5,6}

我希望算法 return p = 2 因为前 3 个出现在数组的位置 2。

对于此算法，假设数组已经排序。

我知道如何使用二进制搜索，但我不知道如何使它成为数组中的第一个 n 而不是它找到的第一个 n。

Answer 1

看看std::lower_bound好像是你要找的

http://en.cppreference.com/w/cpp/algorithm/lower_bound

Answer 2

您只需要稍微修改二分查找就可以让您的 answer.I 编写一个程序来完成所需的工作。

#include<bits/stdc++.h>
using namespace std;

int main()
{
    int no,x;
    int A[12345];
    cout<<"Enter no of array elements : ";
    cin>>no;
    cout<<"Enter array elements : ";
    for (int i=0;i<no;i++)
    {
        cin>>A[i];
    }
    cout<<"Enter no to be searched for : ";
    cin>>x;
    int low = 0;
    int high = no-1;
    while(low<high)
    {
        int mid = low + (high-low)/2;
        if (A[mid]>=x)
        {
            high = mid;
        }
        else
        {
            low = mid+1;
        }
    }
    cout<<"Found at : "<<high;
    return 0;
}

Answer 3

# Binary Search First Element function
def BSFE(begin, end, array, num):
    if end-begin <= 1:
        if array[begin] == num:
            return begin
        elif array[end] == num:
            return end
        else:
            return -1
    else: 
        mid = (begin + end) >> 1;
        if array[mid] >= num:
            return BSFE(begin, mid, array, num)
        else:
            return BSFE(mid, end, array, num)

# main
array = [1, 2, 3, 3, 3, 3, 3, 3, 3, 4, 5, 6]
n = 3
print(BSFE(0, len(array)-1, array, n))

写入python。如果你只会c++，你可以把它当作一段伪代码。这就像归并排序的简化版。

第一个数字 =n 的 C++ 搜索算法

C++ Searching Algorithm for the 1st number =n

c++

binary-search