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

87 阅读 0 评论 58 点赞

我是靠谱客的博主仁爱灰狼，这篇文章主要介绍20天力扣算法刷题计划-第一天二分查找算法第 1 天二分查找，现在分享给大家，希望可以做个参考。

算法

力扣 (LeetCode)

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

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

第 1 天二分查找

704. 二分查找https://leetcode-cn.com/problems/binary-search/

我的代码

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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++

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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. 第一个错误的版本https://leetcode-cn.com/problems/first-bad-version/

标准答案

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 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. 搜索插入位置https://leetcode-cn.com/problems/search-insert-position/我的代码

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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;
}

标准答案

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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，它成立的条件为：