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

入门级题目。

思路有两个：

1 二分法查找到该数值，然后前移到比前面的数大的位置。如果没有找到就返回第一个比该数值大的数的下标。

2 可以二分法查找，不过稍微修改一下，例如查找1,3,5,6；那么两个坐标位置是0和3，然后计算中间位置m = (0+3)/2；但是这里要修改为(0+3+1)/2；这个是关键的地方。因为这样就截去了大于等于这个值的数，那么最后循环返回前面的指针（下标），就可以找到第一个大于等于该数值的下标了。

第一个思路很简单，这里只用了第二个思路，下面是二分法递归查找：

	int searchInsert(int A[], int n, int target) 
	{
		return lowerBound(A, 0, n-1,  target);
	}

	int lowerBound(int A[], int front, int back, int tar)
	{
		if (front > back) return front;
		int mid = front + ((back-front+1)>>1);
		if (A[mid] < tar)
			return lowerBound(A, mid+1, back, tar);
		return lowerBound(A, front, mid-1, tar);
	}

下面是非递归的：

class Solution {
public:
	int searchInsert(int A[], int n, int target) 
	{
		int first = 0;
		while (n>0)
		{
			//注意：移位操作的优先级，注意都加括号
			int mid = first + (n>>1);
			if (A[mid] < target)
			{
				first = mid+1;
				n -= (n>>1)+1;
			}
			else n >>= 1;
		}
		return first;
	}
};

2014元旦更新：

二分截断法：

	int searchInsert3(int A[], int n, int target) 
	{
		int low = 0, up = n-1, mid = 0;
		while (low <= up)
		{
			mid = low +((up-low)>>1);
			if (A[mid] >= target) up = mid-1;
			else low = mid+1;
		}
		return low;
	}

不能再改进的程序了

//2014-1-26 update
	int searchInsert(int A[], int n, int target) 
	{
		int low = 0, up = n-1;
		while (low <= up)
		{
			int mid = low + ((up-low)>>1);
			if (A[mid] >= target) up = mid-1;
			else low = mid+1;
		}
		return low;
	}