搜索插入位置（easy）

更好的閱讀體驗應該是：

審題-思考
答題
整理-歸納

一、題目

LeetCode題目鏈接：35.搜索插入的位置

給定一個排序陣列和一個目標值，在陣列中找到目標值，并回傳其索引，如果目標值不存在于陣列中，回傳它將會被按順序插入的位置，

你可以假設陣列中無重復元素，

示例 1:

輸入: [1,3,5,6], 5
輸出: 2

示例 2:

輸入: [1,3,5,6], 2
輸出: 1

二、題解

分析題干

分析題目很重要，每次閱讀題目都要感謝當年做的那么多閱讀理解，本題中，我們得知：

陣列是排過序的陣列
無重復元素

題解一（暴力法）

提到暴力法，就是頻繁的使用遍歷，且沒有所謂的“套路”，從上倒下透漏出的都是實在！

時間復雜度：O(n)
空間復雜度：O(1)

思路

找到第一比 target 大的元素，它的下標，就是要答案，

實作

var searchInsert = function(nums, target) {
  const len = nums.length;
  for (let i = 0; i < len; i++) {
    if (nums[i] >= target) {
      return i;
    }
  }
  return len;
};

題解二（二分法）

在一個排序的陣列查找，我們可以使用二分法

我們的目的是：查找一個下標index,我們要找的nums[index] <= target的第一個值，

如果找不到，就回傳陣列的長度

時間復雜度：O(log(n))
空間復雜度：O(1)

var searchInsert = function(nums, target) {
  const len = nums.length;
  let left = 0; //左邊界
  let right = len - 1; // 右邊界
  let ans = len; // 回傳值，注意如果目標不在陣列中，回傳陣列的長度
  while (left <= right) {
    mid = ((right - left) >> 1) + left;
    if (target <= nums[mid]) {
      // 證明左邊界在陣列內部
      ans = mid; // 更新回傳值
      right = mid - 1;
    } else {
      left = mid + 1;
    }
  }
  return ans;
};