Search Insert Position

Easy

Given a sorted array 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 may assume no duplicates in the array.

Example 1:

Input:
 [1,3,5,6], 5

Output:
 2

Example 2:

Input:
 [1,3,5,6], 2

Output:
 1

Example 3:

Input:
 [1,3,5,6], 7

Output:
 4

Example 4:

Input:
 [1,3,5,6], 0

Output:
 0

Analysis

此题用Template 1，2都能比较简洁地得到答案。

其实要找的是第一个恰好比target大的数的index。

用template#1，最后剩余2个数的情况下，left在倒数第一循环中，因为right-left=1，所以mid其实就是left，因为比target小，则循环跳出后left其实就变成left+1，比target大了。

Solution

Template #1

class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (target == nums[mid]) {
                return mid;
            } else if (target < nums[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        return left;
    }
}

Template #2

class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0, right = nums.length;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (target == nums[mid]) {
                return mid;
            } else if (target < nums[mid]) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }

        return left;
    }
}

Template #3

class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left + 1< right) {
            int mid = left + (right - left) / 2;
            if (target == nums[mid]) {
                return mid;
            } else if (target < nums[mid]) {
                right = mid;
            } else {
                left = mid;
            }
        }

        if (target > nums[right]) {
            return right + 1;
        }
        if (target > nums[left]) {
            return left + 1;
        }
        return left;
    }
}