如果您比较聪明，可以定义两个不同的二进制搜索功能。一个将返回搜索到的值的第一个外观的索引，另一个将返回搜索到的值的最后一个外观的索引。根据对二进制搜索的了解，您应该能够确定比较的最大和最小数目。

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

**更新

好的，这是一个二进制搜索，以查找元素在数组中的首次出现。我将为您提供一个递归函数（您当然可以进行迭代，并以其他方式对其进行优化）。这将在int数组a中搜索int
val。另外，我也不小心寻找中点（如果数组真的很大，可能会有问题）。

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

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