20天力扣算法刷题计划-第一天二分查找

偏执的太偏执、 2022-09-11 12:20 157阅读 0赞

# 算法 #

力扣 (LeetCode)

在数学和计算机科学之中，算法是一个被定义好的、计算机可施行之指示的有限步骤或次序，常用于计算、数据处理和自动推理。作为一个有效方法，算法被用于计算函数，它包含了一系列定义清晰的指令，并可于有限的时间及空间内清楚的表述出来。

[「算法」 - 学习计划 - 力扣（LeetCode）全球极客挚爱的技术成长平台][- _ - _LeetCode]

# 第 1 天  二分查找 #

[704. 二分查找![icon-default.png_t_L892][]https://leetcode-cn.com/problems/binary-search/][704. _icon-default.png_t_L892_https_leetcode-cn.com_problems_binary-search]

我的代码

int search(int* nums, int numsSize, int target){
    //已知数组地址以及数组个数和目标数字
    //可用二分查找法
    int mid=numsSize/2,left=0,right=numsSize-1;
    //比较
    while(left<=right){
        if(nums[mid]==target)return mid;
        else if(nums[mid]<target){
            left=mid+1;
            mid=(left+right)/2;
        }
        else if(nums[mid]>target)
            right=mid-1;
            mid=(left+right)/2;
        }
        return-1;
    }

标准答案C++

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

[278. 第一个错误的版本![icon-default.png_t_L892][]https://leetcode-cn.com/problems/first-bad-version/][278. _icon-default.png_t_L892_https_leetcode-cn.com_problems_first-bad-version]

标准答案

// The API isBadVersion is defined for you.
    // bool isBadVersion(int version);
    
    int firstBadVersion(int n) {
        int left = 1, right = n;
        while (left < right) {  // 循环直至区间左右端点相同
            int mid = left + (right - left) / 2;  // 防止计算时溢出
            if (isBadVersion(mid)) {
                right = mid;  // 答案在区间 [left, mid] 中
            } else {
                left = mid + 1;  // 答案在区间 [mid+1, right] 中
            }
        }
        // 此时有 left == right，区间缩为一个点，即为答案
        return left;
    }

取平均数防止溢出：左+（右-左）/2

注意答案的取值范围，不要为了编程连基本的数学思维都没有了

[35. 搜索插入位置![icon-default.png_t_L892][]https://leetcode-cn.com/problems/search-insert-position/][35. _icon-default.png_t_L892_https_leetcode-cn.com_problems_search-insert-position]我的代码

int searchInsert(int* nums, int numsSize, int target){
        int left=0;
        int right=numsSize-1;
        //防止不在数组范围内
        if(target<nums[left])return 0;
        if(target>nums[right])return right+1;
    
        int mid=left+(right-left)/2;
        while(right-left>1){
            if(target==nums[mid])return mid;
            else if(target<nums[mid]){
                right=mid;
                mid=left+(right-left)/2;
            }
            else{
                left=mid;
                mid=left+(right-left)/2;
            }
        }
        if(target==nums[left])return left;
        else return right;
    }

标准答案

int searchInsert(int* nums, int numsSize, int target) {
        int left = 0, right = numsSize - 1, ans = numsSize;
        while (left <= right) {
            int mid = ((right - left) >> 1) + left;
            if (target <= nums[mid]) {
                ans = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }

思路与算法

假设题意是叫你在排序数组中寻找是否存在一个目标值，

那么训练有素的读者肯定立马就能想到利用二分法在 O(log⁡n)的时间内找到是否存在目标值。

但这题还多了个额外的条件，即如果不存在数组中的时候需要返回按顺序插入的位置，

那我们还能用二分法么？答案是可以的，我们只需要稍作修改即可。

考虑这个插入的位置 pos，它成立的条件为：

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA56We6L-55bCP5Y2S_size_11_color_FFFFFF_t_70_g_se_x_16][]

其中 nums代表排序数组。

由于如果存在这个目标值，

我们返回的索引也是 pos，

因此我们可以将两个条件合并得出最后的目标：

「在一个有序数组中找第一个大于等于 target的下标」。

问题转化到这里，直接套用二分法即可，

即不断用二分法逼近查找第一个大于等于 target的下标 。

下文给出的代码是笔者习惯的二分写法，ans 初值设置为数组长度可以省略边界条件的判断，

因为存在一种情况是 target大于数组中的所有数，此时需要插入到数组长度的位置。

[- _ - _LeetCode]: https://leetcode-cn.com/study-plan/algorithms/?progress=eca2yqi
[icon-default.png_t_L892]: /images/20220828/65e286b5dd004dfab2d83e740de1df47.png
[704. _icon-default.png_t_L892_https_leetcode-cn.com_problems_binary-search]: https://leetcode-cn.com/problems/binary-search/
[278. _icon-default.png_t_L892_https_leetcode-cn.com_problems_first-bad-version]: https://leetcode-cn.com/problems/first-bad-version/
[35. _icon-default.png_t_L892_https_leetcode-cn.com_problems_search-insert-position]: https://leetcode-cn.com/problems/search-insert-position/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA56We6L-55bCP5Y2S_size_11_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/1fc5f4770ec2481a8a5d96126c10ad13.png