的问题是延长二进制搜索算法找到一个目标值的所有出现在排序后的数组中最有效的方式。 具体地说，该算法的输入是：（1）排序的整数阵列，其中一些数字可以出现一次以上，和（2）一目标整数被搜索。该算法的输出应的一对索引值，指示数组中的整数的首次和最后出现，如果它确实发生。 该人士$ ​​C $ C可能是在C＃，C，C ++。

The problem is to extend the binary search algorithm to find all occurrences of a target value in a sorted array in the most efficient way. Concretely speaking, the input of the algorithm are (1) a sorted array of integers, where some numbers may appear more than once, and (2) a target integer to be searched. The output of the algorithm should be a pair of index values, indicating the first and last occurrence of the integer in the array, if it does occur. The source code could be in c#, c, c++.

还有什么是我们可能需要寻找的指标比较的最大和最小数量。

Also what is the max and min number of comparisons that we might need to find the indexes.

推荐答案

如果你是一个小聪明，你可以定义两个不同的二进制搜索功能。一个将返回的搜索的第一次出现的索引值，另一个将返回的搜索值的最后一次亮相。从你的二进制搜索的知识，你应该能够确定最大和比较的最低数量。

If you are a little clever you can define two different binary search functions. One will return the index of the first appearance of the searched for value and the other will return the last appearance of the searched for value. From your knowledge of binary search, you should be able to determine the maximum and minimum number of comparisons.

使用两个二进制搜索应该是最快的方法，平均在我看来。举例来说，如果你只使用一个二进制搜索找到的第一个项目和线性搜索之后最糟糕的情况是，如果整个功能是相同的值。对于长度10000的阵列，这将同时使用两个二进制搜索会给在最坏的情况下为相同的阵列28的比较给出在最坏的情况下10013比较。当然，使用阵列的大小相同，为二进制/线性搜索方法最好的情况下会是14比较而对于两个二进制搜索方法的情况下，最好的是26比较

Using two binary searches should be the fastest method on average in my opinion. For instance, if you use just one binary search to find the first item and search linearly afterwards the worst case would be if the entire function is the same value. For an array of length 10000, this would give 10013 comparisons in the worst case while using two binary searches would give 28 comparisons in the worst case for the same array. Of course, using the same size of array, the best case for the binary/linear search method would be 14 comparisons while the best case for two binary searches method is 26 comparisons.

**更新

好了，这是一个二进制搜索找到一个元素的数组中的第一次亮相。我给你一个递归函数（你当然可以让它反复并以其他方式优化这一点）。这种搜索的数组整数的整型VAL。另外，我一直没小心发现的中点（如果数组是真正大的可能有问题）。

Okay, here is a binary search to find the first appearance of an element in an array. I'll give you a recursive function (you can of course make it iterative and optimize this in other ways). This searches for the int val in the array a of ints. Also, I haven't been careful about finding the midpoint (if the array is really large there could be problems).

int bs1(int a[], int val, int left, int right)
{
    if(right == left) return left;
    int mid = (right+left)/2;

    if(val > a[mid]) return bs1(a, val, mid+1, right);
    else return bs1(a, val, left, mid);
}

不过，你应该检查你正在返回一个索引，它实际上指的是正确的值，因为如果val不是数组中，返回的指数将对应于下一个元素比VAL大之后。

However, you should check after you are returned an index that it actually refers to the correct value because if val is not in the array, the returned index will to correspond to the next element larger than val.

一些小的改动，以这将使一个函数，找到最后一个元素。的关键在于正确使用比较这样做的，记住的是整数除法总是截断。

A few minor changes to this will make a function that finds the last element. The keys to doing this are using the comparators correctly and remembering that integer division always truncates.