高效算法在O(log(N))时间内找到排序数组中在一定范围内的整数数量？

Question

我遇到了一个必须在O(logn)中完成的面试问题

给定排序的整数数组和数字,找到数组中数字的开始和结束索引.

Ex1: Array = {0,0,2,3,3,3,3,4,7,7,9} and Number = 3 --> Output = {3,6} 

Ex2: Array = {0,0,2,3,3,3,3,4,7,7,9} and Number = 5 --> Output = {-1,-1} 

我试图找到一个有效的算法,但这么胖也没有成功.

Answer 1

您可以使用二分搜索的概念来查找起始索引和结束索引：

• 要找到起始索引，请将数组减半，如果值等于或大于输入 number，则对数组的下半部分重复，否则对上半部分重复。当到达大小为 1 的数组时停止。
• 要找到起始索引，请将数组减半，如果值大于输入 number，则重复数组的下半部分，否则重复上半部分。当到达大小为 1 的数组时停止。

请注意，当我们到达大小为 1 的数组时，我们可能是输入数字旁边的一个单元格，因此我们检查它是否等于输入数字，如果不等于，我们通过在找到的索引中加/减 1 来修复索引。

findStartIndex(int[] A, int num)
{
    int start = 0; end = A.length-1;

    while (end != start) 
    {
        mid = (end - start)/2;

        if (A[mid] >= num)
            end = mid;
        else
            start = mid;
    }

    if(A[start] == num) 
        return start;
    else 
        return start+1;
}

findEndIndex(int[] A, int num)
{
    int start = 0; end = A.length-1;

    while (end != start) 
    {
        mid = (end - start)/2;

        if (A[mid] > num)
            end = mid;
        else
            start = mid;
    }

    if(A[start] == num) 
        return start;
    else 
        return start-1;
}

以及整个过程：

int start = findStartIndex(A, num);

if (A[start]!=num) 
{ 
     print("-1,-1"); 
}
else
{
     int end = findEndIndex(A, num);
     print(start, end);
}