如果你有点聪明，你可以定义两个不同的二进制搜索function。 一个将返回搜索值的第一次出现的索引，另一个将返回搜索值的最后一次出现。 根据您对二进制搜索的了解，您应该能够确定最大和最小比较次数。

在我看来，使用两个二进制搜索应该是平均最快的方法。 例如，如果您只使用一个二进制搜索来查找第一个项目并在之后线性搜索，则最坏的情况是整个函数是相同的值。 对于长度为10000的数组，这将在最坏的情况下进行10013次比较，而使用两次二进制搜索将在最坏的情况下为同一arrays进行28次比较。 当然，使用相同大小的数组，二进制/线性搜索方法的最佳情况是14次比较，而两种二进制搜索方法的最佳情况是26次比较。

**更新

好的，这是一个二进制搜索，用于查找数组中元素的第一个外观。 我会给你一个递归函数（你当然可以迭代并以其他方式优化它）。 这将在int的数组a中搜索int val。 另外，我没有注意找到中点（如果arrays非常大，可能会出现问题）。

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的下一个元素。

对此进行一些细微的更改将使函数找到最后一个元素。 这样做的关键是正确使用比较器并记住整数除法总是截断。

对于C ++，您可以查找std::equal_range()及其复杂性要求。 只要您对基本算法感兴趣，无论实现的语言用途如何，都应适用相同的一般规则。

如果不编写自己的二进制搜索算法，通过重复调用标准算法，这很容易做到。

 // some curly-bracket language: // int BinarySearch(sortedList, searchIndex, searchLength, valueToFind) // returns the zero-based index of the item in the list, or a negative value // if the item is not found int inner = BinarySearch(list, 0, listSize, value); if(inner < 0){ // handle case where value is not found in list } int bottom = inner, top = inner; while(true){ int i = BinarySearch(list, 0, bottom, value); if(i < 0) break; bottom = i; } while(true){ int i = BinarySearch(list, top + 1, listSize - top - 1, value); if(i < 0) break; top = i; } // bottom and top now hold the bounds of all instances of value in list 

这与您使用自定义算法获得的效率非常接近，除了您有更多的函数调用开销。

至于比较的数量，我不得不考虑更难以确定，但我认为它只是2 * log ₂ N，其中N是列表中的项目数。

编辑

呸! 它不是2 * log ₂ N，因为与自定义算法不同，它不会逐步排除列表的某些部分。 似乎¹最大比较计数是（log ₂ N-0.5）* log ₂ N.对于具有2 ^30个元素的列表（对于2 ²⁰ N进行390次比较，对于2 ¹⁰ N进行390次比较），这仍然只有885次比较，但我们可以做得更好。

 // int Compare(a, b) // returns 0 if a and b are equal, // a negative value if a < b, or // a positive value if a > b int start = 0, end = listSize, inner; while(true){ if(end == start){ // handle case where value is not found in list } inner = (start + end) / 2; int cmp = Compare(list[inner], value); if(cmp == 0) break; if(cmp < 0) start = inner + 1; else end = inner; } int top = inner, bottom = inner; while(true){ if(start >= bottom) break; inner = (start + bottom) / 2; int cmp = Compare(list[inner], value); if(cmp == 0) bottom = inner; else start = inner + 1; } while(true){ if(end - 1 <= top) break; inner = (top + 1 + end) / 2; int cmp = Compare(list[inner], value); if(cmp == 0) top = inner; else end = inner; } 

这将最多进行2 * log ₂ N比较。 2 ³⁰项将需要最多60次比较，2 ²⁰项将需要最多40次比较等。

_{¹我通过实验确定了这一点。 我不够聪明，无法用数学方法解决这个问题。}

您可以在Bentley Programming Pearls和Knuth的Vol.3：排序和搜索中找到关于此的讨论。

以下是C ++中的一个实现： http ： //the-algo-blog.blogspot.com/2011/06/binary-search-to-find-last-and-first.html

问题中最有效的部分没有干净的答案。 这将取决于预期有多少具有相同值的条目。 如果只是在找到一个元素之后在数组的两个直接中进行线性搜索将是你最快的选择，但如果你期望很多具有相同值的条目你可以做一些二进制搜索来找到开始结束指数。

免责声明：未经测试; 它旨在表明这个想法，而不是直接用作生产代码

 int org = binarySearch(array,value) //do the binary search and find on element int min = org-delta; //delta is some constant based on how many elemts are to be expected int max = org; min = min < 0 ? 0 : min; int search= min; bool latestWasHit = false; while(search > 0) { if(search+1 == max) return max; if(array[search] != value) { min = search; search = search + (max-search)/2 } else { max = search; search = (search-min)/2; } } 

然后是上限的反向。 然而，在比简单的线性搜索更快之前，它将需要相当多的元素。

我想普通算法会有这样的东西：

 if(value == test) return; if(value < test) min = i; if(value > test) max = i; 

一旦您使用它来查找其中一个值，请使用您当前必须查找提示的最小值和最大值执行两次稍微模式化的二进制搜索。

要找到最顶层的替换上面的：

 if(value <= test) min = i; if(value > test) max = i; 

最底层替换为：

 if(value >= test) max = i; if(value < test) min = i; 

请注意，使用此方法没有提前返回，您只需继续操作，直到最小值和最大值分别为一个或多个，我想您可以添加另一个检查

 if(value == test and arr[i-1] != test) return; 

等等

我创建了两个二进制搜索方法，分别返回第一次和最后一次出现。

上述就是C#学习教程：扩展二进制搜索算法以查找要在数组中搜索的键值的第一个和最后一个索引分享的全部内容，如果对大家有所用处且需要了解更多关于C#学习教程，希望大家多多关注---计算机技术网(www.ctvol.com)!

 public static void main(String[] args) { int a[] ={1,2,2,2,2,2,5,5,6,8,9,10}; System.out.println(5+" first = "+first(a, 5, 0, a.length-1)); System.out.println(5+" last = "+right(a, 5, 0, a.length-1)); System.out.println(1+" first = "+first(a, 1, 0, a.length-1)); System.out.println(1+" last = "+right(a, 1, 0, a.length-1)); System.out.println(2+" first = "+first(a, 2, 0, a.length-1)); System.out.println(2+" last = "+right(a, 2, 0, a.length-1)); System.out.println(10+" first = "+first(a, 10, 0, a.length-1)); System.out.println(10+" last = "+right(a, 10, 0, a.length-1)); System.out.println(8+" first = "+first(a, 8, 0, a.length-1)); System.out.println(8+" last = "+right(a, 8, 0, a.length-1)); System.out.println(11+" first = "+first(a, 11, 0, a.length-1)); System.out.println(11+" last = "+right(a, 11, 0, a.length-1)); } private static int first(int [] a, int x, int l, int h){ if(l>h){ return -1; } int mid = (hl)/2+l; if(a[mid] == x && (mid==0 || a[mid-1] != x) ){ return mid; }else if(a[mid] == x){ return first(a, x, l, mid-1); }else if(a[mid]>x){ return first(a, x, l, mid-1); }else{ return first(a, x, mid+1, h); } } private static int right(int [] a, int x, int l, int h){ if(l>h){ return -1; } int mid = (hl)/2+l; if(a[mid] == x && (mid==a.length-1 || a[mid+1] != x) ){ return mid; }else if(a[mid] == x){ return right(a, x, mid+1, h); }else if(a[mid]>x){ return right(a, x, l, mid-1); }else{ return right(a, x, mid+1, h); } } Output: 1 first = 0 1 last = 0 2 first = 1 2 last = 5 10 first = 11 10 last = 11 8 first = 9 8 last = 9 11 first = -1 11 last = -1