(算法:二分查找)在排序数组中,找出给定数字出现的次数

时间:2021-02-14 11:05:50

题目:

在排序数组中,找出给定数字出现的次数

思路:

既然出现排序数组,很容易想到二分查找,时间复杂度为O(logn);

先通过二分查找找到最左边出现该数字的下标left(如果没找到,则返回-1),然后通过二分查找找到最右边出现该数字的下表right(如果没找到,则返回-1),然后right-left+1就是出现的次数;

代码:

#include <iostream>

using namespace std;

int BinarySearchCount(int *array,int len,int data){
    if(len<1) return -1;
    int left=0;
    int right=len-1;
    int mid;
    int leftIndex=-1;

    // find the left index
    while(left<=right){
        mid=left+((right-left)>>1);
        if(array[mid]==data){
            leftIndex=mid;
            right=mid-1;
        }
        else if(array[mid]<data)
            left=mid+1;
        else
            right=mid-1;
    }

    // find the right index
    left=0;
    right=len-1;
    int rightIndex=-1;
    while(left<=right){
        mid=left+((right-left)>>1);
        if(array[mid]==data){
            rightIndex=mid;
            left=mid+1;
        }
        else if(array[mid]<data)
            left=mid+1;
        else
            right=mid-1;
    }

    if(leftIndex!=-1 && rightIndex!=-1)
        return rightIndex-leftIndex+1;
    else
        return 0;
}

int main()
{
    int arr[]={0,1,2,3,3,3,3,3,3,3,4,5,6,7,13,19};
    int len=sizeof(arr)/sizeof(arr[0]);
    cout << BinarySearchCount(arr,len,18) << endl;
    return 0;
}