LeetCode:Search Insert Position,Search for a Range (二分查找,lower_bound,upper

LeetCode:Search Insert Position,Search for a Range (二分查找,lower_bound,upper_bound)

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume no duplicates in the array.

Here are few examples.
[1,3,5,6], 5 → 2
[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4
[1,3,5,6], 0 → 0

这就是普通的二分查找,需要注意的地方代码注释中都有。其中特别注意的是：middle=（low+high）/ 2 ，可能会溢出，可以替换为middle = low + ((high - low)>>2);

class Solution {
public:
    int searchInsert(int A[], int n, int target) {
        //二分查找
        int low = 0, high = n-1;//注意这里high是初始化为n-1
        while(low <= high)//注意这里是<=号
        {
            //int middle = (low + high) / 2;
            int middle = low + ((high - low)>>2); //可以防止low + high 溢出
            if(A[middle] < target)
                low = middle + 1;
            else if(A[middle] > target)
                high = middle - 1;
            else return middle;
        }
        return low;//注意返回值是low
    }
};

根据程序员编程艺术第二十五章：Jon Bentley：90%无法正确实现二分查找, 如果high初始化为n, 那么while判断语句就应该是low<high, 下面的A[middle] > target分支中,就应该是high = middle

Search for a Range

Given a sorted array of integers, find the starting and ending position of a given target value.

Your algorithm's runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].

看到这个有没有想到STL中的equal_range函数,这个函数是调用lower_bound和upper_bound, 下面我们仿照STL的实现。相比上一题的二分查找，lower_bound当A[middle] == target时，继续向左半部分查找，它返回的是第一个不小于目标数的元素位置；upper_bound当A[middle] == target时，继续向右半部分查找，它返回的是第一个大于目标数的元素位置。本文地址

class Solution {
public:
    vector<int> searchRange(int A[], int n, int target) {
        vector<int> res(2, -1);
        int low = 0, high = n-1;
        while(low <= high)
        {
            int middle = low + ((high - low)>>2);
            if(A[middle] < target)
                low = middle + 1;
            else if(A[middle] > target)
                high = middle - 1;
            else
            {
                res[0] = lowerBound(A, low, middle - 1, target);
                res[1] = upperBound(A, middle + 1, high, target) - 1;
                return res;
            }
        }
        return res;
    }
    
    //找到范围内[left,right]内第一个不小于target的元素
    int lowerBound(int A[], int left, int right, int target)
    {
        int low = left, high = right;
        while(low <= high)
        {
            int middle = low + ((high - low)>>2);
            if(A[middle] < target)
                low = middle + 1;
            else high = middle - 1;
        }
        return high + 1;//注意这里返回值不是low
    }
    //找到范围[left,right]内第一个大于target的元素
    int upperBound(int A[], int left, int right, int target)
    {
        int low = left, high = right;
        while(low <= high)
        {
            int middle = low + ((high - low)>>2);
            if(A[middle] <= target)
                low = middle + 1;
            else high = middle - 1;
        }
        return low;
    }
};