专栏首页光城(guangcity)基于二分搜索法的floor与ceil

基于二分搜索法的floor与ceil

导语:刷算法,练内功!

by 光城

基于二分搜索法的floor与ceil

1.基本的二分搜索

在闭区间[left,right]范围内查找target。

class Solution {
public:
    int search1(vector<int>& nums, int target) {
        if (nums.size() == 0) return -1;
        
        int left = 0, right = nums.size()-1;
        
      	// left与right均不会越界,可以取等
        while (left <= right) {
            int mid =left+ (right-left) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {	
                left = mid + 1;	// mid处理过了,需要mid+1
            } else if (nums[mid] > target) {
                right = mid-1;	// mid处理过了,需要mid-1
            }
        }
        return -1;
    }
};

如果上述right改为nums.size(),判断与right均会发生变化:

此时处理的范围为[left,right)

class Solution {
public:
    int search2(vector<int>& nums, int target) {
        if (nums.size() == 0) return -1;
        
        int left = 0, right = nums.size();
        
      	// right会越界
        while (left < right) {
            int mid =left+ (right-left) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {	
                left = mid + 1;	// mid处理过了,需要mid+1 left不会越界
            } else if (nums[mid] > target) {
                right = mid;	// 处理范围为[left,right),right为开区间,不可取得right,一定要维护[left,right)这个条件不变
            }
        }
        return -1;
    }
};

上述都比较简单,现在我们考虑有如下例子:

vector<int> nums={1,2,2,2,2,3,5};
int target=2;

此时使用上述二分查找算法,搜索出来的index为3。那如果我想要获取最左侧等于target的index或最右侧等于target的index呢?此时上述算法失效!

2.最左侧index

所谓最左侧index为第一个等于target对应的index

class Solution {
public:
    int search3(vector<int>& nums, int target) {
        if (nums.size() == 0) return -1;
        int left = 0, right = nums.size()-1;

        while (left <= right) {
            int mid =left+ (right-left) / 2;
            if (nums[mid] == target) {
                right=mid-1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid-1;
            }
        }
        
        if(left==nums.size()) return -1;	// 如果最后left==nums.size(),表示nums中的所有元素都小于target,查找失败!
        return nums[left] == target ? left : -1;
    }
};

3.最右侧index

所谓最右侧index为最后一个等于target对应的index

class Solution {
public:
    int search4(vector<int>& nums, int target) {
        if (nums.size() == 0) return -1;
        int left = 0, right = nums.size()-1;

        while (left <= right) {
            int mid =left+ (right-left) / 2;
            if (nums[mid] == target) {
                left = mid + 1; // 注意
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid-1;
            }
        }
        
        if(right<0) return -1;	// 或者写if(left==0) return -1; 如果right<0,那么此时nums中所有元素均大于target
        return nums[right] == target ? right : -1;
    }
};

测试上述算法:

int main() {
    vector<int> nums={1,2,2,2,2,3,5};
    int target=2;
    cout<<Solution().search1(nums,target)<<endl;       // 3
    cout<<Solution().search2(nums,target)<<endl;       // 3
    // 寻找第一个等于target的index,最左侧index
    cout<<Solution().search3(nums,target)<<endl;       // 1
    cout<<Solution().search4(nums,target)<<endl;       // 4
    return 0;
}

测试成功。

4.floor

对于上述最左侧index,我们可以将这个算法的返回值进行修改,这样就得到了我们想要的floor函数,floor函数定义是:当存在大量重复元素时,floor找的是第一个,当不存在指定的元素时,floor找的是比其小最大的一个。

注意边界,当所有元素小于target时,返回的index为最后一个index,当所有元素大于target时,返回-1.

class Solution {
public:
    int floor1(vector<int>& nums, int target) {
        if (nums.size() == 0) return -1;
        int left = 0, right = nums.size()-1;

        while (left <= right) {
            int mid =left+ (right-left) / 2;
            if (nums[mid] == target) {
                right=mid-1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid-1;
            }
        }
        // 所有元素均大于target
        if (right < 0) return -1;
        // 所有元素均小于target
        if (left == nums.size()) return left - 1;
        return nums[left] == target ? left : left-1;
    }
};

将该算法使用另外一种写法:

使用(left,right]定义

int floor2(vector<int>& nums, int target) {{

    // 寻找比target小的最大索引
    int left = -1, right = nums.size()-1;
    
    // (left,right]
    while( left < right ){
        // 使用向上取整避免死循环
        int mid = left + (right-left+1)/2;
        if( nums[mid] >= target )
            right = mid - 1;
        else
            left = mid;
    }
    // 如果该索引+1就是target本身, 该索引+1即为返回值
    if( left + 1 < nums.size() && nums[left+1] == target )
        return left + 1;
    // 否则, 该索引即为返回值
    return left;
}

5.ceil

对于上述最右侧index,我们可以将这个算法的返回值进行修改,这样就得到了我们想要的ceil函数,ceil函数定义是:当存在大量重复的元素时,ceil找的是第一个。当不存在指定的元素时,ceil是比其大最小的一个。

注意边界,当所有元素小于target时,返回的index为最后一个index,当所有元素大于target时,返回0.

class Solution {
public:
    int ceil1(vector<int>& nums, int target) {
        if (nums.size() == 0) return -1;
        int left = 0, right = nums.size()-1;

        while (left <= right) {
            int mid =left+ (right-left) / 2;
            if (nums[mid] == target) {
                left = mid + 1; // 注意
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid-1;
            }
        }

        // 所有元素均大于target
        if (right < 0) return 0;
        // 所有元素均小于target
        if (left == nums.size()) return left - 1;
        return nums[right] == target ? right : right+1;
    }
};

将该算法使用另外一种写法:

使用(left,right]定义

int ceil2(vector<int>& nums, int target) {

    // 寻找比target大的最小索引值
    int left = 0, right = nums.size()-1;
    while( left < right ){
        // 使用普通的向下取整即可避免死循环
        int mid = left + (right-left)/2;
        if( nums[mid] <= target )
            left = mid + 1;
        else // arr[mid] > target
            right = mid;
    }
    // 如果该索引-1就是target本身, 该索引+1即为返回值
    if( right - 1 >= 0 && nums[right-1] == target )
        return right-1;
    // 否则, 该索引即为返回值
    return right;
}

6.全部算法测试

int main() {
    vector<int> nums = {1, 2, 2, 2, 2, 3, 5};
    int target = 2;
    cout << Solution().search1(nums, target) << endl;       // 3
    cout << Solution().search2(nums, target) << endl;       // 3
    // 寻找第一个等于target的index,最左侧index
    cout << Solution().search3(nums, target) << endl;       // 1
    cout << Solution().search4(nums, target) << endl;       // 4
    cout << Solution().ceil1(nums, 0) << endl;			// 0
    cout << Solution().ceil2(nums, 0) << endl;			// 0
    cout << Solution().ceil1(nums, 4) << endl;			// 5
    cout << Solution().ceil2(nums, 4) << endl;			// 5
    cout << Solution().ceil1(nums, 6) << endl;			// 6
    cout << Solution().ceil2(nums, 6) << endl;			// 6

    cout << Solution().floor1(nums, 0) << endl;			// -1
    cout << Solution().floor2(nums, 0) << endl;			// -1
    cout << Solution().floor1(nums, 4) << endl;			// 5
    cout << Solution().floor2(nums, 4) << endl;			// 5
    cout << Solution().floor1(nums, 6) << endl;			// 6
    cout << Solution().floor2(nums, 6) << endl;			// 6
    return 0;
}

本文分享自微信公众号 - 光城(guangcity),作者:lightcity

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-10-14

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 螺旋矩阵你听过?

    昨天满课,我还是坚持来刷题了,写文时间是晚上10点45,刷题时间是10点,今日题目leetcode上的螺旋矩阵,这道题思路简单,实现困难,,对于考研的同学建议仔...

    公众号guangcity
  • 回归Android,继续刷题

    这两天要做个安卓项目,哎,我之前是做安卓开发的,做了半年多,后面就没做了,距离现在至少1年半有余。

    公众号guangcity
  • 详解数组刷题上

    一、初始定义及原地修改1.283. 移动零2.27. 移除元素3.26. 删除排序数组中的重复项4.80. 删除排序数组中的重复项 II二、基础思想应用1.75...

    公众号guangcity
  • [Leetcode][python]Find First and Last Position of Element in Sorted Array/在排序数组中查找元素的第一个和最后一个位置

    给定一个按照升序排列的整数数组 nums,和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

    后端技术漫谈
  • 二分查找两种实现,附详细注释

    链接:https://leetcode-cn.com/problems/binary-search

    double
  • Binary Search - 33. Search in Rotated Sorted Array

    Suppose an array sorted in ascending order is rotated at some pivot unknown to y...

    用户5705150
  • 【剑指offer:在排序数组中查找数字】搜索左右边界:从两边向中间、二分查找

    二分查找一般用来查找数字在有序数组中是否出现过。进一步想,它可以用来不断在子序列中搜索对应数字。所以,我们就可以用它来向左边子序列中不断搜索,确认左边界;同样的...

    心谭博客
  • OMG,我从来没想过,二分查找还有诗?!

    二分查找是极其简单容易理解的一种算法,但它的变形与细节也是极其繁杂的,一不小心就容易踩坑。

    五分钟学算法
  • 二分查找算法细节详解

    我相信对很多读者朋友来说,编写二分查找的算法代码属于玄学编程,虽然看起来很简单,就是会出错,要么会漏个等号,要么少加个 1。

    haifeiWu
  • LeetCode<二分搜索> 33 & 81 Search in Rotated Sorted Array I&II

    Suppose an array sorted in ascending order is rotated at some pivot unknown to y...

    大学里的混子

扫码关注云+社区

领取腾讯云代金券