【算法挨揍日记】day09——35. 搜索插入位置、69. x 的平方根

蔚落 2024-02-27 05:49 5阅读 0赞

![9d816b8f83fd4349a63cf98d63cc42d2.png][]

## 35. 搜索插入位置 ##

[35. 搜索插入位置][35.]

### 题目描述： ###

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 `O(log n)` 的算法。

![533d5e09c3f94c1694698e363b78a7b8.png][]

### 解题思路： ###

> 本题有两种可能：
> 
>  *  当t（target）在数组中，返回其下标
>  *  t不在数组中，返回它应该插入的位置的下标
> 
> 可以将数组看成两个区。【数组<t】【数组>=t】
> 
> 这就变成了找第二个数组【数组>=t】的第一个位置
> 
> 也就变成了需要左端点的问题了
> 
> 当循环结束后，left==right了，此时需要考虑边界问题，也就是nums【left】和t的关系，如果小于则返回left的下一个位置

### 解题代码： ###

class Solution {
    public:
        int searchInsert(vector<int>& nums, int target) {
            int left=0,right=nums.size()-1;
            while(left<right)
            {
                int mid=left+(right-left)/2;
                if(nums[mid]==target)return mid;
                if(nums[mid]<target)left=mid+1;
                if(nums[mid]>target)right=mid;
            }
            //此时left==right,考虑边界问题
            if(nums[left]<target)return left+1;
            return left;
        }
    };

--------------------

## 69. x 的平方根 ##

[69. x 的平方根][69. x]

### 题目描述： ###

给你一个非负整数 `x` ，计算并返回 `x` 的 **算术平方根** 。

由于返回类型是整数，结果只保留 **整数部分** ，小数部分将被 **舍去 。**

**注意：**不允许使用任何内置指数函数和算符，例如 `pow(x, 0.5)` 或者 `x ** 0.5` 。

![743285c68002439390bbd9aab14a7e5a.png][]

### 解题思路： ###

> 本题可以变成我们从0到x中找一个数mid，mid的平方最接近x，也可以等于x
> 
> 将0-x数组分为两部分，一部分【0，mid】【mid+1，x】因此就变成找左区间的右端点了

### 解题代码： ###

class Solution {
    public:
        int mySqrt(int x) {
            long long left=0,right=x;
            while(left<right)
            {
                long long mid=left+(right-left+1)/2;
                if(mid*mid<x) left=mid;
                if(mid*mid==x)return mid;
                if(mid*mid>x) right=mid-1;
            }
        
            return right;
        }
    };

### ![885d1f08c460402d831122c3a6530fd3.gif][] ###

[9d816b8f83fd4349a63cf98d63cc42d2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/27/0a4a9b411d6740b2b7e6f135563b75a3.png
[35.]: https://leetcode.cn/problems/search-insert-position/
[533d5e09c3f94c1694698e363b78a7b8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/27/17d0277a2921489a80319fddb36f2718.png
[69. x]: https://leetcode.cn/problems/sqrtx/
[743285c68002439390bbd9aab14a7e5a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/27/b5d0faa2bedf40b4812bc3e7d5dafec2.png
[885d1f08c460402d831122c3a6530fd3.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/27/7596fc68ecbd4c289c3ea5aa95bd844f.png