c - 只有两次比较的迭代二分查找?

标签 c binary-search

调整迭代二进制搜索代码,使其只使用两次比较而不是三个(在 主 while 循环)。 *注:三个比较在while循环中,两个if语句 在循环内。

#include <stdio.h>

int ItBinarySearch(int arr[], int len, int target) {

    int first = 0;
    int last = len-1;

    while (first <= last){
        // Assert: array is sorted
        int mid = (first+last) / 2;

        if (target == arr[mid])
            return 1;

        if (target < arr[mid])
            last = mid-1;

        else first = mid+1;
    }
    return 0;
}

int main(void){
    int arr[6]={0,1,2,3,4,5};
    int len=sizeof(arr)/sizeof(arr[0]);
    int target = 4;
    printf("%d\n",ItBinarySearch(arr,len,target));
}

最佳答案

提示:尝试将其中一个 if/else 语句移出循环。哪个 if/else 最有可能成为算法在语句之外仍然有效的候选者?

关于c - 只有两次比较的迭代二分查找?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/49060796/

相关文章:

python - Python中的二分查找,更优雅的方法?

c++ - 以高效的方式从 Node.js 运行 C 或 C++ 代码

c - fwrite() 和文件损坏

c - 快速平方根优化?

algorithm - 这种类型的二进制搜索有名称吗?

c++ - 为什么会出现段错误以及如何解决它

c# - 查找排序数组中的所有差异

algorithm - 修改二进制搜索以查找下一个比键更大的项目

c - Zilog Z80 操作码实现

在 C 中检查可用的堆栈大小