LeetCode題解：Search Insert Position

LeetCode題解：Search Insert Position

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.

Here are few examples.
[1,3,5,6], 5 → 2
[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4
[1,3,5,6], 0 → 0

題意：給定有序數組和目標元素，找該元素的插入位置，如果該元素沒有在數組中，找到它應該插入的位置（保持原數組有序）

解決思路：二分查找

代碼：

public class Solution {
    public int searchInsert(int[] nums, int target) {
        int count = nums.length;
        int left = 0;
        int step = 0;
        int mid = 0;

        while(count > 0){
            step = count >> 2;
            mid = left + step;

            if(nums[mid] < target){
                left = mid + 1;
                count -= (step + 1);
            }else{
                count = step;
            }
        }

        return left;
    }
}