学步园

http://haixiaoyang.wordpress.com/category/search-binary-search/

/*
Suppose we are given an array A[1 .. n] with the special property that A[1] ≥A[2] and
A[n − 1] ≤A[n]. We say that an element A[x] is a local minimum if it is less than or equal
to both its neighbors, or more formally, if A[x − 1] ≥A[x] and A[x] ≤A[x + 1]. For example,
there are five local minima in the following array:
9 7 7 2 1 3 7 5 4 7 3 3 4 8 6 9
We can obviously find a local minimum in O(n) time by scanning through the array. Describe
and analyze an algorithm that finds a local minimum in O(log n) time
*/

//Same as previous binary search, based on location! When if returns?
//When it should search left, when it should search right?
int findLocalMin(int a[], int n)
{
	assert(a && n > 2);

	int nBeg = 0;
	int nEnd = n-1;

	while (nBeg <= nEnd)
	{
		int nMid = nBeg + (nEnd - nBeg)/2;

		//This logic is straight forward
		if (nMid > 0 && nMid < n-1 && a[nMid-1] >= a[nMid] && a[nMid+1] >= a[nMid])
			return nMid;

		//The most important thing is how to come up with the logic below:
		//1: should search left if in the right most point, obvious
		//2: UNDER THE SITUATION THAT nMid is not a middle point,
		//   can judge the trend by (nMid, nMid+1) or (nMid-1, nMid)
		//   take advantage of nMid != n-1 when reaching the right half of logic
		if ((nMid == n-1) || (a[nMid] <= a[nMid+1])) //Pitfall, less equal than not less!!
			nEnd = nMid - 1;
		else nBeg = nMid + 1; //Otherwise logic
	}

	return -1;
}

一定要注意这个条件，a[1] >=a[2]    a[n-1] <= a[n]

那么在此区间内肯定至少有一个局部最小点

如果  a[mid-1]<=a[mid] <= a[mid+1]

则在beg-mid区间肯定有局部最小

如果a[mid-1]>= a[mid]>=a[mid+1]

则在mid-end区间肯定有局部最小

如果 a[mid-1]<= a[mid]>=a[mid+1]

在两个区间内均存在局部最小