基于二分搜索法的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)

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

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

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券