相关疑难解决方法(0)

我正在学习考试,并发现了这个问题.

您将获得一个排序的整数数组,例如:

{-5, -5, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 67, 67, 99}

写一个方法:

Public static int count (int[] a, int x)

返回数字'x'在数组中的次数.

例如:

x = -5, it returns 2
x = 2, it returns 5
x = 8, it returns 0

我需要尽可能高效地写它,请不要给我答案(或者如果你愿意的话写下来,但我不会看),我的想法是做二分搜索,然后去两边(向后)我找到的值和索引号,返回正确的答案,我的问题是:

1. 这是最有效的方式吗？
2. 在最坏的情况下,它不会是O(n)吗？(当数组填充一个数字时) -

如果是这样 - 那我为什么要进行二分搜索呢？

一次比较每次迭代二进制搜索有什么意义？你能解释它是如何工作的吗？

我在排序数组中多次出现一个键,我想对它们执行二进制搜索,正常的二进制搜索为具有多次出现的键返回一些随机索引,其中我想要该键的最后一次出现的索引.

int data[] = [1,2,3,4,4,4,4,5,5,6,6];
int key = 4;
int index = upperBoundBinarySearch(data, 0, data.length-1, key);

Index Returned = 6