如何以最快的方式检查两个给定位置之间是否存在数字？

Question

我给了一个数字说N和它在数组中的相应位置.说给出的位置(指数)是:

4 5 8 11 13 15 21 28

我给了两个位置(指数)说x和y.设x = 7,y = 13.

我需要找到x和y之间有多少次出现的数字(包括y> = x).与上面的例子中一样,数字存在于位置x和y之间的位置8,11和13处,因此答案是3.

一个简单的方法是天真的O(n)算法,但我想利用这样的事实,即poistions总是按升序给出.我认为以修改的方式应用二进制搜索可能有所帮助,但我面临着麻烦.

// P is the array that stores positions(indices) of number
int start=0,End=n-1; // n is the size of array P
int mid=(start+End)/2;
int pos1=0,pos2=0;
while(End>start)
{
   mid=(start+End)/2;  
   if(P[mid]>=x && P[mid-1]<x && flag1!=0)
    {
        pos1=mid;
        flag1=0

    }
    if(P[mid]<=y && P[mid+1]>y && flag2!=0)
    {
        pos2=mid;
        flag2=0;
    }
    else if (P[mid]<x)
        start=mid;
    else
        End=mid;
 }
    int Number_Of_Occurence=(pos2-pos1);

你能否说一下我的代码可能出错的地方？

Answer 1

您可以利用STL库.std::lower_bound或std::upper_bound想到.

两者在具有随机迭代器的已排序容器上具有对数复杂性.

例如:

#include <iostream>   
#include <algorithm>  
#include <vector>     

int main() {

  std::vector<int> v = {4, 5, 7, 8, 11, 13, 15, 21, 28};

  int low_value = 7;
  int high_value = 13;

  auto low = std::lower_bound(v.begin(), v.end(), low_value);
  auto high = std::upper_bound(v.begin(), v.end(), high_value);

  std::cout << std::distance(low, high) << " elements in interval ["
            << low_value << ", " << high_value << "]" << std::endl;

  return 0;
}