二分查找详解 (闭区间)

2019-11-20 language algorithm leetcode

之前的文章已经详细介绍了二分查找，不过使用的是闭区间，这里再介绍一下开区间的实现细节，两种方法基本没有区别，可以选择其中一个。

基本搜索

这里简单介绍另外的一种更新策略，对应的搜索空间为 [left, right) ，同时需要修改两个点。

  • while (left < right) 对应终止条件是 left = right，而搜索空间为 [left, right) 空，可以正常终止。
  • 更新时采用 right = mid 以及 left = mid + 1，因为在确认 mid 不满足条件后，对应的搜索空间应该是 [left, mid) 或 [mid + 1, right) 。

综上，可以将代码修改为。

int binary_search(int *array, int length, int target)
{
        int left, right, mid;

        left = 0;
        right = length;
        while (left < right) { // [left, right)
                mid = left + (right - left) / 2;
                if (array[mid] == target)
                        return mid;
                else if (array[mid] < target)
                        left = mid + 1;
                else if (array[mid] > target)
                        right = mid;
        }

        return -1;
}

仍然以之前的示例为例，这里不再查找 23 而是 10 ，查找顺序如下。

binary search example right open

左边界搜索

这里直接列出代码。

int left_bound(int *array, int length, int target)
{
        int left, right, mid;

        left = 0;
        right = length;
        while (left < right) { // [left, right)
                mid = left + (right - left) / 2;
                if (array[mid] == target)
                        right = mid;
                else if (array[mid] < target)
                        left = mid + 1;
                else if (array[mid] > target)
                        right = mid;
        }
        //return left; // how many items less than target.
        if (left >= length || array[left] != target)
                return -1;
        return left;
}

右边界搜索 

int right_bound(int *array, int length, int target)
{
        int left, right, mid;

        left = 0;
        right = length;
        while (left < right) { // [left, right)
                mid = left + (right - left) / 2;
                if (array[mid] == target)
                        left = mid + 1;
                else if (array[mid] < target)
                        left = mid + 1;
                else if (array[mid] > target)
                        right = mid;
        }
        //return left; // how many items less or equal to target.
        if (left <= 0 || array[left - 1] != target)
                return -1;
        return left - 1;
}