提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  其他

当前栏目

在排序数组中查找数字target之二分查找

数组 排序
2023-04-18 15:22:11 时间

问题：在排序数组中查找数字target之二分查找剑指 Offer 53 - I. 在排序数组中查找数字 I - 力扣（LeetCode）

自己写的低效率：

class Solution {
public:
    int search(vector<int>& nums, int target) {
        unordered_map<int,int>mp;
        for(auto& num:nums){
            if(mp[num]) mp[num] += 1;
            else mp[num] = 1;
        }
        if(mp[target]) return mp[target];
        else{
            return 0;
        }
    }
};

方法一：二分法，查找target的左右边界，return right-left-1；两次循环二分查找。第一次是nums[m] <= target ，跳出循环的结果即为确定target的右边界；第二次 nums[m] < target，确定target的左边界；等号即为target的部分，若存在。 

时间复杂度：O(log N); 空间复杂度：O(1);

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int i = 0,j = nums.size()-1;
        while(i <= j){
            int m = (i+j)/2;
            if(nums[m] <= target) i = m+1;
            else j = m-1;
        }
        int right = i;//右边界。这个肯定比target大，nums[j]则为最右的target,若存在。
        if(j>=0 && nums[j]!= target) return 0;//不存在target,直接返回
        i = 0;
        while(i<=j){
            int m = (i+j)/2;
            if(nums[m] < target) i = m+1;
            else j = m -1;
        }
        int left = j;
        return right - left - 1;
    }
};

 二分法优化：两次查找右边界，第一次查找target的右边界，第二次查找target-1的右边界；return right1-right2；

class Solution {
public:
    int search(vector<int>& nums, int target) {
        return right_side(nums,target)-right_side(nums,target-1);
    }
private:
    int right_side(vector<int>& nums,int target){
        int i = 0, j = nums.size()-1;
        while(i<=j){
            int m = (i+j)/2;
            if(nums[m]<=target) i = m+1;
            else j = m -1;
        }
        return i;
    }
};

丢失的数字为 右子数组的首位元素对应的索引，因为是对中位数作比较，相等的时候进行 i 递增加一；不等的时候即为递增后的i，

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int i = 0,j = nums.size()-1;
        while(i<=j){
            int m = (i+j)/2;
            if(nums[m] == m) i = m+1;
            else j = m -1;
        }
        return i;
    }
};

 

相关文章