c 上的二分查找，while 循环

Question

在 C 上的二进制搜索代码中有一些我没有得到的东西。

int binarySearch(int a[], int n, int x)
{
   int low=0, mid, high=n-1;
   while(low <= high)
   {
        mid = (low + high) / 2;
        if (x < a[mid])
            high = mid - 1;
        else if (x > a[mid])
         low = mid + 1;
       else
         return mid;
   }
   return -1;
}

为什么while循环while(left<=right)不能写： while(left<right)？这种变化会影响事情吗？

Answer 1

举个简单的案例

int a[1] = {5};
printf("%d\n", binarySearch(a, 1, 5));

使用while(low < high)，代码打印 -1（未找到 - 错误答案）。

使用while(low <= high)，代码打印 0（找到 - 正确答案）。

Answer 2

第 1 部分 - 此具体问题的快速解答

这不是二分查找的完整总结，但我会简短地总结一下以解决这个问题。
这两个 while 循环条件的主要区别是
1. low( left) 和high( right) 指针相应更新。“相应”请参见第 3 部分。 2. 假设( ) 和( )
的边界没有重复 3. 假设数组中存在目标，则在 [ , ]范围内进行搜索，两端包括的。 相比之下，二分搜索在 [ , )范围内进行，右/高端除外。对于上/右范围/部分中的目标的二分搜索，它们总是会错过最后/右/高处的检查，即最后一个( ) 停止的地方。为了使范围完全覆盖，通常建议根据最后一个( )指针再进行一次判断。LOWLEFTHIGHRIGHT


while(low <= high)LOWHIGH
while(low < high)LOWHIGHlowleftlowleft

第 2 部分 - 一般准则

可能是任意的一般准则：
1. 当处理目标肯定存在于数组中，并且用于搜索的数组不包含重复项的情况时，while(low <= high)首选
2. 当处理目标不一定存在于数组中的情况时，并且数组可能包含重复项，while(low < high)建议这样做。

第 3 部分 - 代码

low( left) 和high( right) 指针“相应地”更新

    public int binarySearch(int[] nums, int target){

        int left = 0, right = nums.length - 1;
        // please pay attention to the initial condition of right(ptr)
        while(left <= right){
            // to floor the mid
            int mid = left + (right - left) / 2;

            // to check whether the middle element is equal to the target in every iteration
            if(nums[mid] == target) return mid;
            else if(target > nums[mid]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return -1;
    }

    public int binarySearch(int[] nums, int target){
        // please pay attention to the initial condition or the right(ptr)
        int left = 0, right = nums.length;

        while(left < right){
            int mid = left + (right - left) / 2;

            // please pay twice attention to the equality case
            if(target > nums[mid]) {
                left = mid + 1;
             } else {
                right = mid;
             }
        }

        return left;
    }

第 4 部分 - 变体，稍微更高级

警告：以下类型可能会引起混淆while(low <= high)：

    public int binarySearchWithFlooringMid(int[] nums, int target){
        // please pay attention to the initial condition of right(ptr)
        int left = 0, right = nums.length - 1;
        while(left <= right){
            // to floor the mid
            int mid = left + (right - left) / 2;

            // to check whether the middle element is equal to the target in every iteration
            if(nums[mid] == target) return mid;
            else if(target > nums[mid]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        return -1;
    }

    public int binarySearchWithCeilingMid(int[] nums, int target){
        int left = 0, right = nums.length - 1;
        while(left <= right){
            // to ceil the mid
            int mid = left + (right - left + 1) / 2;

            // to check whether the middle element is equal to the target in every iteration
            if(nums[mid] == target) return mid;
            else if(target > nums[mid]) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }

        return -1;
    }

对于类型while(low < high)

    public int binarySearchLeftmost(int[] nums, int target){
        int left = 0, right = nums.length;

        while(left < right){
            int mid = left + (right - left) / 2;

            // please pay twice attention to the equality case
            if(target > nums[mid]) {
                left = mid + 1;
             } else {
                 right = mid;
             }
        }

        return left;
    }

    public int binarySearchRightmost(int[] nums, int target){
        int left = 0, right = nums.length;

        while(left < right){
            int mid = left + (right - left) / 2;

            // please pay twice attention to the equality case
            if(target < nums[mid]) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }

        return right - 1;
    }

这篇文章并未涵盖二分搜索方面的所有情况。还有更复杂的要求，我将在掌握它们后更详细地讨论。