扩展二进制搜索算法以查找要在数组中搜索的键值的第一个和最后一个索引
问题是扩展二进制搜索算法，以最有效的方式查找排序数组中所有出现的目标值。具体地说，算法的输入是（1）排序的整数数组，其中一些数字可能出现多次，以及（2）要搜索的目标整数。该算法的输出应该是一对索引值，指示该整数在数组中的第一个和最后一个出现（如果确实出现）。源代码可以是c＃，c，c
++。
另外，查找索引可能需要的最大和最小比较数目是多少？
回答：
如果您比较聪明，可以定义两个不同的二进制搜索功能。一个将返回搜索到的值的第一个外观的索引，另一个将返回搜索到的值的最后一个外观的索引。根据对二进制搜索的了解，您应该能够确定比较的最大和最小数目。
我认为，平均而言，使用两个二进制搜索应该是最快的方法。例如，如果仅使用一个二进制搜索来查找第一项，然后线性搜索，则最坏的情况是整个函数的值相同。对于长度为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的元素。
对此进行一些小的更改将使函数找到最后一个元素。这样做的关键是正确使用比较器，并记住整数除法总是会被截断。
以上是 扩展二进制搜索算法以查找要在数组中搜索的键值的第一个和最后一个索引 的全部内容， 来源链接： utcz.com/qa/398380.html
