[LeetCode]Search Insert Position

Binary Search，最后lo的位置就是插入应该在的位置。
证明：当lo == hi的时候跳出循环，这时候有三种情况：

• lo的位置的值正好就是target，这时候直接return，就是我们要找的位置
• lo的位置的值大于target，这时候执行hi  = mid - 1，然后跳出循环，这个时候lo的位置也是插入的时候应该在的位置，因为target小是小于A[lo]位置最大的值，target应该被插入后应该在lo的位置
• lo的位置的值小于target，这时候执行lo = mid + 1然后跳出循环。由于现在target是大于A[lo]的最小值，插入后应该在的位置是上一次循环lo的后面(现在lo = mid  +1)，所以就是lo现在的位置。

代码如下：

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

view raw search insertion position iterative.java hosted with ❤ by GitHub