0035 - Search Insert Position

大意

搜尋已經排列好的陣列，找出目標數字，並回傳該數字所在的  Index

如果找不到目標數字，就回傳該插入在哪邊的 Index。

以下是 LeetCode 的三個範例：

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

個人想法

使用 Binary Search 就可以滿足要求。

不過當所有數字都找不到時，要再判斷一次中位數跟目標數哪個數字比較大，再依照狀況回傳中位數 Index + 1 還是不用 +1:

class Solution {
    public int searchInsert(int[] nums, int target) {
        // Binary search
        int left = 0;
        int right = nums.length - 1;
        int mid = 0;

        while(left <= right){
            mid = (left + right) / 2;
            if(nums[mid] > target){
                // 比 mid 要再往前一格（因為 target 比較小）
                right = mid - 1;
            } else if (nums[mid] < target){
                // 比 mid 要再往後一格（因為 target 比較大）
                left = mid + 1;
            } else {
                return mid;
            }
        }

        // 跳出迴圈，代表還找不到結果
        // 再比較一下目前的中位數，如果比中位數還大，就代表要插入到他後面的位置
        // 否則就是插入中位數的當前位置
        if(nums[mid] < target){
            return mid + 1;
        } else {
            return mid;
        }
    }
}