35.搜索插入位置

链接：35.搜索插入位置
难度：Easy
标签：数组、二分查找
简介：给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

题解 1 - typescript

• 编辑时间：2021-07-22
• 执行用时：80ms
• 内存消耗：39.5MB
• 编程语言：typescript
• 解法介绍：二分查找。

function searchInsert(nums: number[], target: number): number {
  let l = 0;
  let r = nums.length - 1;
  while (l <= r) {
    const mid = (l + r) >> 1;
    const midNum = nums[mid];
    if (midNum < target) l = mid + 1;
    else if (midNum > target) r = mid - 1;
    else return mid;
  }
  return l;
}

题解 2 - c

• 编辑时间：2021-11-30
• 内存消耗：6.6MB
• 编程语言：c
• 解法介绍：二分查找。

int searchInsert(int* nums, int numsSize, int target){
    int m, l = 0, r = numsSize - 1;
    if (nums[l] > target) return 0;
    if (nums[r] < target) return numsSize;
    while (l < r) {
        m = (l + r) >> 1;
        if (nums[m] == target) {
            l = m;
            break;
        }
        if (nums[m] >= target) r = m;
        else l = m + 1;
    }
    return l;
}

题解 3 - typescript

• 编辑时间：2020-07-17
• 执行用时：80ms
• 内存消耗：38.6MB
• 编程语言：typescript
• 解法介绍：二分查找。

function searchInsert(nums: number[], target: number): number {
  function _search(l: number, r: number): number {
    if (l >= r) return l;
    const mid = (l + r) >> 1;
    const num = nums[mid];
    if (num < target) return _search(mid + 1, r);
    else if (num > target) return _search(l, mid);
    else return mid;
  }
  return _search(0, nums.length);
}

题解 4 - cpp

• 编辑时间：2021-12-20
• 执行用时：4ms
• 内存消耗：9.5MB
• 编程语言：cpp
• 解法介绍：二分查找。

class Solution {
   public:
    int searchInsert(vector<int>& nums, int target) {
        int l = 0, r = nums.size(), m;
        while (l < r) {
            m = (l + r) >> 1;
            if (nums[m] >= target)
                r = m;
            else
                l = m + 1;
        }
        return l;
    }
};