只有两次比较的迭代二分查找？

Question

调整迭代二进制搜索代码，使其只使用两次比较而不是三个（在主 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));
}

Answer 1

提示：尝试将 if/else 语句之一移出循环。哪个 if/else 是最有可能的候选者，如果它在语句之外，算法仍然有效？

只有两次比较的迭代二分查找？

Iterative binary search with only two comparisons?

c

binary-search