Search Insert Position

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

思路：

（1）題意為給定一個已排序的數組和一個整數，求該整數在數組中的位置。

（2）由於數組是已排序的，本題可以通過“二分查找”算法來尋找目標整數的位置。但需要注意對邊界值判斷，當目標整數小於數組第一個元素時，應返回0；當目標整數大於數組最後一個元素時，返回數組長度加1。該題還是比較簡單，詳情見下方代碼。

（3）希望本文對你有所幫助。

算法代碼實現如下：

/**
 * @author liqq
 */
public class SearchInsert {
	public int searchInsert(int[] A, int target) {
		int high = A.length - 1;
		int low = 0;
		int mid = (high + low) / 2;

		if (A[low] > target)
			return 0;
		if (A[high] < target)
			return high + 1;

		while (mid >= 0 || mid <= high) {
			if (A[mid] > target) {
				if (A[mid] > target && A[mid - 1] < target) {
					return mid;
				} else {
					mid--;
				}
			} else if (A[mid] < target) {
				if (A[mid] < target && A[mid + 1] > target) {
					return mid + 1;
				} else {
					mid++;
				}
			} else {
				return mid;
			}

		}
		return -1;
	}
}