C++搜索算法的第一位数字= N

Question

我想，类似的方式工作，其中我公司拥有一批n二进制搜索算法，假设3和排列如下：

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

我希望算法返回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++，你可以把它当作一段伪代码。这就像合并排序的简化版本。