35.搜索插入位置

2023-12-30 12:28:36

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

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

示例 1:

输入: nums = [1,3,5,6], target = 5
输出: 2

示例?2:

输入: nums = [1,3,5,6], target = 2
输出: 1

示例 3:

输入: nums = [1,3,5,6], target = 7
输出: 4

提示:

  • 1 <= nums.length <= 104
  • -104 <= nums[i] <= 104
  • nums?为?无重复元素?的?升序?排列数组
  • -104 <= target <= 104

这个题是经典的二分算法,但是略有改进。

二分查找(Binary Search)是一种在有序数组中查找特定元素的高效算法。它的基本思想是将目标值与数组中间的元素进行比较,如果目标值小于中间元素,则在数组的左半部分继续查找,否则在右半部分查找,不断缩小搜索范围,直到找到目标值或确定目标值不存在为止。

二分查找也叫折半查找,比如在一个有序的数组里面找到目标值,它是一种查询效率比较高的算法,时间复杂度O(logn)。比如在下面数组找到 6.首先在定位到两侧,也就是最大值和最小值。并找到中间和目标值比较。

中间值是 5,比目标值更小,就要缩小范围,中间值作为最小值,在中间值右边的区域再找到中间值和目标值比较。

以此类推,一直缩小范围,直到找到目标值,或者搜索完数据。

本题就是在二分的基础上进行改进,本质和折半插入排序一致,在最后返回时,要返回low或者high+1,即要插入的位置。

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

文章来源:https://blog.csdn.net/L6666688888/article/details/135303478
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。