35. Search Insert Position

題目：
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

想法：
依序檢查等於、小於、大於三種可能，並簡化

程式碼：
方法一：按部就班

class Solution {
    public int searchInsert(int[] nums, int target) {
        int i = 0;
        //判斷三種可能（等於、小於、大於）
        while (i < nums.length){
            if(nums[i] == target){ //等於目標值即回傳i
                return i;
            }else if (nums[i] < target){ //小於目標值即不做事，等迴圈i++
            }else if  (nums[i] > target){ //大於目標值即回傳i，因需插入此位置
                return i;
            }i++;
        }
        return i;
    }
}

方法二：化簡

class Solution {
    public int searchInsert(int[] nums, int target) {
        int i = 0;
        //想法，希望能簡化程式碼
        //!()拆開，因此需要相反
        //while (i < nums.length !(nums[i] == target || nums[i] > target)){
        //    i++;
        //}
        while (i < nums.length && nums[i] < target) i++;
        return i;
    }
}

實際操作：

nums = [1,3,5,6],
目標 = 2

STEP1 檢查三種可能
「等於」直接回傳索引值
「小於」不做事
「大於」回傳索引值，因此目標值最適合放入該位置
若檢查不到，則i++，重新尋找

STEP2 回傳結果i