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;
	}