（1） 二分查找：

使用二分查找（Binary Search）的前提有：（1）线性表必须是关键码有序（通常是从小到大有序）。（2）其次，线性表必须是顺序存储。所以链表不能采用二分查找。

二分查找（Binary Search）基本思想：在有序表中，取中间记录作为比较对象，若给定值与中间记录的关键字相等，则查找成功；若给定值小于中间记录的关键字，则在中间记录的左半区继续查找；若给定值大于中间记录的关键字，则在中间记录的右半区继续查找。不断重复上述过程，知道查找成功，或者所有查找区域无记录，查找失败为止。

例题：现有这样一个有序表数组{1, 16, 24, 35, 47, 59, 62, 73, 88, 99}，对它进行查找是否存在62这个数。算法实现如下：

#include 
using namespace std;

/*
函数名：	BinarySearch
函数功能：	在数组array内查找值为key的元素，返回该元素所在数组的位置
函数参数：	int *array	数组指针
			int length	数组长度
			int key		要查找的key值。
返回值：	如果key存在数组内，返回其在数组中的位置；否则返回-1。
*/
int BinarySearch(int *array, int length, int key)
{
	/* 对参数的合法性进行判断 */
	if (array == NULL || length <= 0)					
	{
		return -1;
	}

	int low, middle, high;
	low = 0;
	high = length - 1;
	while (low <= high)
	{
		/* middle取low和high中间元素 */
		middle = low + (high - low) / 2;				

		/* array[middle] > key，故在middle的左边查找key */
		if (key < array[middle])						
		{
			high = middle - 1;
		}
		/* array[middle] < key，故在middle的右边查找key */
		else if (key > array[middle])					
		{
			low = middle + 1;
		}
		/* array[middle] = key，故返回middle */
		else											
		{
			return middle;
		}
	}

	/* 如果数组中不存在key值，则返回-1 */
	return -1;											
}

void Test(const char *testName, int *array, int length, int key, int expectedIndex)
{
	cout << testName << " : ";
	if (BinarySearch(array, length, key) == expectedIndex)
	{
		cout << "Passed." << endl;
	}
	else
	{
		cout << "Failed." << endl;
	}
}

int main()
{
	int array[] = {1, 16, 24, 35, 47, 59, 62, 73, 88, 99};
	Test("Test1", array, sizeof(array) / sizeof(*array), 62, 6);
	Test("Test2", array, sizeof(array) / sizeof(*array), 1, 0);
	Test("Test3", array, sizeof(array) / sizeof(*array), 99, 9);
	Test("Test4", array, sizeof(array) / sizeof(*array), 100, -1);
	Test("Test5", array, sizeof(array) / sizeof(*array), 0, -1);

	return 0;
}

下面我们考虑，如何使用二分查找的基本思想来解决以下问题。

例1：把一个数组最开始的若干元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3，4，5，1，2}为{1，2，3，4，5}的一个旋转，该数组的最小值为1。（剑指offer，面试题8，页数：66）

旋转数组的性质有：旋转数组实际上将其分成两个子数组，前面子数组是递增的，后面子数组也是递增的，但是前面子数组的元素大于或等于后面子数组的元素，其中最小元素在后面子数组的第一个元素。例数如组{3， 4， 5， 1， 2}分成两个子数组{3,4,5}和{1, 2}，则最小值为1。

我们可以尝试使用二分查找的思想，用两个指针分别指向数组的第一个元素和最后一个元素。按照题目中旋转的要求，则第一个元素应该是大于或者等于最后一个元素。

然后我们找到中间元素，如果该中间元素位于前面的递增子数组，那么它应该大于或者等于第一个指针指向的元素。此时数组中最小的元素应该位于该中间元素后面，所以我们把第一个指针指向该中间元素，缩小查找范围。移动之后的第一个指针仍然位于前面的递增子数组之中。

同样，如果中间元素位于后面的递增子序列，那么它应该小于或者等于第二个指针指向的元素。此时该数组中最小的元素应该位于该中间元素的前面。我们可以把第二个指针指向该中间元素，这样也可以缩小查找范围。移动之后的第二个指针仍然位于后面的递增子数组之中。

不管是移动第一个指针，还是第二个指针，查找范围都会缩小到原来的一半。接下来我们再用更新之后的两个指针，重新做新的一轮的查找。

按照上述的思路，第一个指针总是指向前面递增数组的元素，而第二个指针总是指向后面递增数组的元素。最终第一个指针将指向前面子数组的最后一个元素，而第二个指针会指向后面子数组的第一个元素。也就是它们最终会指向两个相邻的元素。而第二个指针指向刚好是最小的元素。这就是循环结束的条件。

这里有一个特殊情况，就是如果中间元素array[middle] == array[low] == array[high]这种情况，如果是这样的话，那我们就只能在low和high之间，遍历查找最小值。

整个算法实现如下：

#include 
using namespace std;


/* 
函数名：	GetMinestValue
函数功能：	获取数组rotatedArray[low...high]之间最小值所在数组的位置。
函数参数：	int *rotatedArray	旋转数组
			int low				查找范围为[low, high]的low
			int high			查找范围为[low, high]的high
返回值：	如果存在，则返回最小值所在数组的位置；否则返回-1。
*/
int GetMinestValue(int *roatedArray, int low, int high)
{
	/* 检测参数的合法性 */
	if (roatedArray == NULL || low < 0 || high < 0 || low > high)
	{
		return -1;
	}

	/* 遍历数组rotatedArray[low...high]，找到最小值所在的位置 */
	int min = low;
	for (int i = low; i <= high; i++)
	{
		if (roatedArray[i] < roatedArray[min])
		{
			min = i;
		}
	}

	return min;
}

/*
函数名：	GetMinestValue
函数功能：	在旋转数组RotatedArray中找到最小值，返回该值所在的位置
函数参数：	int *rotatedArray	旋转数组指针
			int length			旋转数组长度
返回值：	如果存在最小值，则返回该值所在位置；否则，返回-1。
*/
int GetMinestValue(int *roatedArray, int length)
{
	/* 检查参数的合法性 */
	if (roatedArray == NULL || length <= 0)
	{
		return -1;
	}

	int low, middle, high;
	low = 0;
	middle = 0;
	high = length - 1;

	/* 这个数组是递增的，旋转0个元素，则直接返回0 */
	if (roatedArray[low] < roatedArray[high])			
	{
		return low;
	}

	while (low < high)
	{
		/* 如果low和high是相邻的，则返回high */
		if (high - low == 1)							
		{
			middle = high;
			break;;
		}

		middle = low + (high - low) / 2;

		/* 如果中间元素和两边元素都相等的情况下，只能循环遍历数组，找到最小的值 */
		if (roatedArray[low] == roatedArray[middle] && roatedArray[middle] == roatedArray[high])
		{

		}

		/* 如果roatedArray[middle] >= roatedArray[low]，说明middle在前面递增子数组，故low = middle */
		if (roatedArray[middle] >= roatedArray[low])
		{
			low = middle;
		}
		/* 如果roatedArray[middle] <= roatedArray[high]，说明middle在后面递增子数组，故high = middle */
		else if (roatedArray[middle] <= roatedArray[high])
		{
			high = middle;
		}
	}

	return middle;
}

void Test(const char *testName, int *rotatedArray, int length, int expectedIndex)
{
	cout << testName << " : ";
	if (GetMinestValue(rotatedArray, length) == expectedIndex)
	{
		cout << "Passed." << endl;
	}
	else
	{
		cout << "Failed." << endl;
	}
}

int main()
{
	int rotatedArray1[] = {1, 2, 3, 4, 5};
	Test("Test1", rotatedArray1, sizeof(rotatedArray1) / sizeof(int), 0);
	int rotatedArray2[] = {3, 4, 5, 1, 2};
	Test("Test2", rotatedArray2, sizeof(rotatedArray2) / sizeof(int), 3);
	int rotatedArray3[] = {1, 1, 1, 0, 1};
	Test("Test3", rotatedArray3, sizeof(rotatedArray3) / sizeof(int), 3);
	int rotatedArray4[] = {5};
	Test("Test4", rotatedArray4, sizeof(rotatedArray4) / sizeof(int), 0);
	return 0;
}

例2：统计一个数字在排序数组中出现的次数。例如输入排序数组{1, 2, 3, 3, 3, 3, 4, 5}和数字3，由于3在这个数组中出现了4次，因此输出4。（剑指offer，面试题38，页数204）

如何查找排序数组中k的个数，首先我们分析如何用二分查找算法在数组中找到第一个k，二分查找算法总是先拿数组中间的数字和k作比较。如果中间的数组比k大，那么k只有可能出现在数组的前半段，下一轮我们只在数组的前半段查找就可以了。如果中间的数字比k小，那么k只有可能出现在数组的后半段，下一轮我们只在数组的后半段查找就可以了。那么如果中间的数字和k相等呢？我们先判断这个数字是不是第一个k。如果位于中间数字的前面一个数字不是k，此时中间的数字刚好就是第一个k。如果位于中间数字的前面一个数字也是K，也就是说第一个k肯定在数组的前半段，下一轮我们仍然需要在数组的前半段查找。

基于这个思路，我们很容易实现该算法找到第一个k：