01 二分查找

二分查找

704. 二分查找

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left{}, right = nums.size() - 1;
        int mid{};
        while(left <= right)
        {
            mid = (left + right) / 2;
            if(nums[mid] > target)
                right = mid - 1;
            else if(nums[mid] < target)
                left = mid + 1;
            else
                return mid;
        }
        return -1;
    }
};

35.搜索插入位置

思路：使用二分查找找到该元素，如果找不到，则应该插入在right+1的位置。

解释：因为二分查找中，right找到的是小于等于target的下标。等于时直接返回mid，小于时返回right+1。

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int left{}, right = nums.size() - 1;
        int mid{};
        while(left <= right)
        {
            mid = (left + right) / 2;
            if(nums[mid] < target)
                left = mid + 1;
            else if (nums[mid] > target)
                right = mid - 1;
            else 
                return mid;
        }
        return right + 1;
    }
};

stl库解法：使用lower_bound函数。

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        auto beginIter = nums.begin();
        return std::distance(beginIter, lower_bound(beginIter, nums.end(), target));
    }
};

34.在排序数组中查找元素的第一个和最后一个位置

思路：使用二分查找获取左边界和右边界。

如果左边界和有边界的值相差小于2，则不存在。

否则返回左边界+1和有边界-1。

核心代码：对二分中的target==nums[mid]进行合并。

如果合并到left+1，则最终会逼近右边界。

如果合并到right+1，则最终会逼近左边界。

class Solution {
private:
    int searchLowIndex(vector<int>& nums, int target)
    {
        int left{}, right = nums.size() - 1;
        int mid{};
        int leftBord = -2;      //test if in range
        while(left <= right)
        {
            mid = left + (right - left) / 2;
            if(nums[mid] < target)
                left = mid + 1;
            else
                leftBord = right = mid - 1;
        }
        return leftBord;
    }

    int searchHighIndex(vector<int>& nums, int target)
    {
        int left{}, right = nums.size() - 1;
        int mid{};
        int rightBord = -2;     //test if in range
        while(left <= right)
        {
            mid = left + (right - left) / 2;
            if(nums[mid] > target)
                right = mid - 1;
            else
                rightBord = left = mid + 1;
        }
        return rightBord;   
    }
    
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int leftIndex = searchLowIndex(nums, target);
        int rightIndex = searchHighIndex(nums, target);
        if(leftIndex == -2 || rightIndex == -2)     //out of range
            return {-1, -1};
        else if(rightIndex - leftIndex >= 2)        //in range and find left and right
            return {leftIndex + 1, rightIndex - 1};
        else                                        //in range but not find
            return {-1, -1};
    }
};

直接使用库函数：

std::lower_bound函数返回一个指向大于或等于给定值的第一个元素的迭代器。如果没有找到符合条件的元素，它将返回指向容器末尾的迭代器。
std::upper_bound函数返回一个指向大于给定值的第一个元素的迭代器。如果没有找到符合条件的元素，它将返回指向容器末尾的迭代器。

注意：

这两个函数，只能保证找到目标值位置或者能插入目标值的位置，因此需要增加一个检验：|| *startIter != target来保证目标值至少存在。
lower_bound找到了返回该元素的迭代器，upper_bound找到了返回该元素后面的一个迭代器。也就是说，这个区间是一个左闭右开的区间。

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        std::vector<int> result = { -1, -1 };

        // 查找起始下标
        auto startIter = std::lower_bound(nums.begin(), nums.end(), target);
        if (startIter == nums.end() || *startIter != target) {
            return result;  // 没有找到目标值，返回{-1, -1}
        }
        int startIndex = std::distance(nums.begin(), startIter);

        // 查找终止下标
        auto endIter = std::upper_bound(nums.begin(), nums.end(), target);
        int endIndex = std::distance(nums.begin(), endIter) - 1;

        // 更新结果
        result[0] = startIndex;
        result[1] = endIndex;

        return result;
    }
};

69.x 的平方根

class Solution {
public:
    int mySqrt(int x) {
        //特殊值
        if(x == 0)  return 0;
        if(x == 1)  return 1;
        
        int left{}, right = x;
        int mid{};
        while(left <= right)
        {
            mid = left + (right - left) / 2;
            if(mid <= x / mid)
                if((mid + 1) > x / (mid + 1))
                    return mid;
                else
                    left = mid + 1;
            else
                right = mid - 1;
        }
        return mid;
    }
};

发布于 2023-07-22