Leetcode - Search Insert Position

[分析] 经典二分查找，下面代码实现了迭代方式，可以验证，若直到循环结束也没有找到目标元素，则left恰好指在比target大的第一个位置， right恰好指在比target小的最后一个位置，因此返回left即可。开始没注意到这个规律，卡在循环结束该返回什么上。

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