C中二进制搜索的第一次和最后一次出现

Question

我试图理解如何修改二进制搜索,它适用于第一次和最后一次出现,当然我可以在网上找到一些代码,但我试图深入理解,这里是一些基本的非递归二进制搜索我发现:

int BinarySearch(int *array, int number_of_elements, int key)
{
    int low = 0, high = number_of_elements-1, mid;
    while(low <= high)
    {
            mid = (low + high)/2;
            if(array[mid] < key)
            {
                    low = mid + 1; 
            }
            else if(array[mid] == key)
            {
                    return mid;
            }
            else if(array[mid] > key)
            {
                    high = mid-1;
            }

    }
    return -1;
}

我需要做哪些修改以及它们背后的逻辑是什么？

编辑:我希望它高效而不是线性完成.

Answer 1

据我了解，如果找到您要查找的元素，一个选择是向左或向右执行线性搜索以查找最后一次出现的第一个元素。

或者，您可以再次使用二分搜索来调整位置，直到下一个位置的元素发生变化。这可以通过修改上面的中间情况来完成；如果找到该元素，则在位置保持不变之前不要返回其位置。