leetCode EASY - Q35.Search Insert Position -
===

---
###### tags: `leetCode`, `練習刷題`,

<br>

## 題目
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.

Example 1:

Input: nums = [1,3,5,6], target = 5
Output: 2
Example 2:

Input: nums = [1,3,5,6], target = 2
Output: 1
Example 3:

Input: nums = [1,3,5,6], target = 7
Output: 4

## 解題：
這題主要是能找到 target 之間對象的index所在。如果在array裡面找到值，那就return當下的 index。
如果沒有的話，例如 target 是 2， 那target要插在1前面，並且返回插入後的index位置。
如果target 超過了 array裡所有的值，那就 返回 array.length + 1

## 我的方法：

var searchInput = function (nums: number[], target: number){
    if(nums.length === 0 || target === 0) return 0;
    
    const left = 0;
    const right = nums.length -1;
    
    while( left <= right ){
        const mid = Math.floor((left + right) /2);
        
        if(nums[mid] === target ) {
            return mid;
        }else if(nums[mid] < target){
            left = mid + 1;
        }else {
            right = mid -1
        }
    }
    return left;
}

## 講解：
我們來用比較的方法，只要left 超過了 right的時候，就結束loop了。
mid絕對沒辦法超過left的值。

初始化: left = 0, right = 3
mid = 1 → nums[mid] = 3, so left = mid + 1 = 2
mid = 2 → nums[mid] = 5, 然後就找到目標了，回傳 mid.

第二組：

nums = [1, 3, 5, 6];
target = 2;

初始化: left = 0, right = 3
mid = 1 → nums[mid] = 3, 因為超過了，所以 right = mid - 1 = 0
mid = 0 → nums[mid] = 1, so left = mid + 1 = 1.

第三組：

nums = [1, 3, 5, 6];
target = 7;

初始化: left = 0, right = 3
mid = 1 → nums[mid] = 3, left = mid + 1 = 2
mid = 2 → nums[mid] = 5, left = mid + 1 = 3
mid = 3 → nums[mid] = 6, left = mid + 1 = 4.

## 別人的解法：

var searchInsert = function (nums, target) {

    for (let i = 0; i < nums.length; i++) {
        if (nums[i] == target)
            return i;
        else if (nums[i] > target) {
            return i;
        }
    }
    return nums.length;
};

## 總結：
我當初做的時候也用 for 迴圈，沒想到 while 也可以，而我太少使用 while 所以也沒想到這方法。
我認為當需要用到比較的時候，都可以想起 while，然後建立left 和 right，和答案 mid 去設計這樣的做法。我覺得別人的解法條件寫的很好，也是可以參考哦！
希望這文章有幫助你學習！我們下篇文章再見！ PEACE！