Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You must write an algorithm with O(log n) runtime complexity.

給定一個有序陣列，陣列中有多個不重複的整數 以及 一個目標值，請回傳目標值在陣列中的索引值。如果陣列中沒有跟目標值相同的整數，則回傳目標值在陣列中插入的位置。

你必須編寫一個算法，其時間複雜度是 O(log n)。

其實這一題在很久之前就寫過了(而且還寫了兩次)，今天就把之前的兩種做法整理一下做個記錄囉!

Binary Search(二分法搜尋)
第一種作法是按照Binary Search(二分法搜尋)的概念解題的，解題思路如下:

1. 先檢查如果 目標值target 比 陣列nums中索引值0 對應的數值還要小，那表示 目標值target 的位置一定會在索引值 0
2. 利用while loop跑迴圈尋找目標值target的位置
3. 每一次的loop，都先算出 起點start與終點end 的中位數 mid 值，並以此作為二分法搜尋的基準。
   • 只要目標值target比中位數 mid 值大，就把start的位置移到中位數mid的右側(縮小下一次要搜尋的範圍)。
   • 反之，只要目標值target比中位數 mid 值小，就把終點end的位置移到中位數mid的位置(縮小下一次要搜尋的範圍)。

瞄一眼程式碼

var searchInsert = function(nums, target) {
     if (target < nums[0]) return 0
     let start = 0
     let end = nums.length 
     while (start < end) {
         const mid = Math.floor((start + end) / 2)
         if (target > nums[mid]) {
             start = mid + 1
         } else {
             end = mid
         }
     }
     return start
};

直覺解法
下面這一版是第一次解題的記錄，當時沒有使用Binary Search(二分法搜尋)所以時間複雜度較高。

1. 宣告res作為檢查目標值target的起點
2. 利用for loop，去比較陣列nums中的每一個值跟目標值target
   • 若目標值target較大，則將res往右側移動，縮小下一次檢查的範圍
   • 反之，如果兩者等值，則回傳當前索引值
3. 如果目標值target在陣列nums中沒有對應等值的索引位置，在for loop中會進不去判斷，res就不會被更新，直到for loop跑完後，回傳res的位置。

(自評: 這個做法明顯比Binary Search(二分法搜尋)效率低)

程式碼

var searchInsert = function(nums, target) {
  // for loop 檢查nums
  let res = 0
  for (let i = 0; i < nums.length; i++) {
    //比較大就往下檢查
    if (nums[i] < target) {
      res++
    //一樣大回傳當前index值
    } else if (nums[i] === target) {
      res = i
    }
  }
  return res
};