35. 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

链接：https://leetcode.com/problems/search-insert-position/

2/11/2017, Java

这道题主要是通过各种例子来想，下标的想法跟之前一样，一定要想清楚这个下标到底是用来做什么的，避免一会儿返回low, 一会儿发现要返回low + 1这种，不然其实是自己对算法也不了解，就是蒙的。

这道题思路主要是如果范围缩小到一个值，怎么判断，所以循环条件不是low <= high，而是low < high，我们把low = high这个条单独拿出来判断。low > high这种是超了边界，就很容易解决。

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