您现在的位置是：首页 > 后台技术 > 数据结构与算法数据结构与算法

搜索插入位置(图文)

第十三双眼睛2023-11-24【数据结构与算法】人已围观

简介搜索插入位置
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。

思路：搜索能想到二分法，当目标值等于中间值的时候，直接返回中间值下标，如果目标值小于中间值，则右边指针移动到中间位置的前一位，如果目标值大于中间值，左边指针移动到中间位置的后一位，如此循环，直到当左边指针位置大于右边指针位置，跳出循环，这时候返回左边指针就是要插入的位置。代码如下：

public int searchInsert(int[] nums, int target) {
   int l = 0;
   int r = nums.length - 1;
   while (l <= r) {
       int mid = (l + r) / 2;
       if (nums[mid] == target) {
           return mid;
       }
       if (target > nums[mid]) {
           l = mid + 1;
       } else {
           r = mid - 1;
       }
   }
   return l;
}

Tags：

很赞哦！ ()

上一篇：移除元素(图文)

下一篇：最后一个单词的长度(图文)