【基础篇 - Day 27】 2023-03-11 35. 搜索插入位置 （05. 双指针）

[threedayAAAAA]

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

请必须使用时间复杂度为 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

来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/search-insert-position 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

[threedayAAAAA]

思路

二分插件

代码

function searchInsert(nums: number[], target: number): number {
    let start = 0
    let end = nums.length - 1
    let midIndex = -1
    while(true){
        midIndex = (start + end) >> 1
        if(nums[midIndex] === target){
            return midIndex
        } 
        if(start === midIndex){
            return target < nums[start] 
                ? start 
                : target > nums[end] 
                    ? end + 1
                    : end
        }
        if(nums[midIndex] > target){
            end = midIndex
        } else {
            start = midIndex
        }

    } 
    return midIndex
};

时空复杂度

• 时间复杂度：O(logn)
• 空间复杂度：O(1)

[MiumMi]

思路

二分法找到对应位置即可

function searchInsert(nums: number[], target: number): number {
  let startIndex = 0;
  let endIndex = nums.length - 1;
  if (nums[startIndex] >= target) {
      return startIndex;
  }
  if (nums[endIndex] < target) {
      return endIndex + 1;
  }
  if (nums[endIndex] === target) {
      return endIndex;
  }
  while (true) {
      const centerIndex = Math.floor((endIndex + startIndex) / 2);
      const middle = nums[centerIndex];
      if (middle === target) {
          return centerIndex;
      }
      if (startIndex === centerIndex) {
        return middle >= target ? startIndex : (nums[endIndex] < target ? endIndex + 1 : endIndex);
      }
      if (middle > target) {
          endIndex = centerIndex;
      } else {
          startIndex = centerIndex;
      }
  }
};

---

分析

时间复杂度: O(logn) 空间复杂度：O(1)

[yunliuyan]

思路

• 二分法
• 首尾指针,head, end，若nums[head] >= target || nums[end] <= target 则返回head | end对应的处理
• 否则 head++, end--，直到head <= end
• 要处理首尾指针遍历完，但还是没找到targe插入位置的场景，比如[1,3]插入2

代码

function searchInsert(nums: number[], target: number): number {
    let head = 0, end = nums.length - 1;

    while(head < end) {
        if (nums[head] >= target)  {
            return head;
        } else if(nums[end] === target) {
            return end;
        } else if(nums[end] < target) {
            return ++end;
        }
        head++;
        end--;
    }
    // 首尾指针遍历完，但还是没找到targe插入位置
    return nums[head] < target ? ++head : head;
};

复杂度分析

• 时间复杂度: O(logn)
• 空间复杂度: O(1)