leetcode-35-search-insert-position

Description

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:

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

Example 2:

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

Example 3:

1 2	Input: [1,3,5,6], 7 Output: 4

Example 1:

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

思路

題意是讓妳從壹個沒有重復元素的已排序數組中找到插入位置的索引。因為數組已排序，所以我們可以想到二分查找法，因為查找到的條件是找到第壹個等於或者大於 target 的元素的位置，所以二分法略作變動即可。

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