学步园

#include <iostream>
using namespace std;

/**
* 二分查找之一： 可以找到连续重复出现的第一个出现的元素
*/
int binarySearch(int a[], int n, int x){
	int l = 0, h = n-1;
	int m;

	while(l <= h){
		m = (l+h)/2;
		if(x <= a[m]) h = m-1;	//如果相同，仍然向前走
		else l = m+1;			//否则向后走
	}

	//如果查找的元素没有连续出现，则取更大的指针l指向的元素
	if(l<n && a[l] == x){
		return l;
	}
	return -1;
}

/**
* 二分查找之二： 相等即返回，不确定返回重复元素的第几个
*/
int binarySearch2(int a[], int n, int x){
	int l=0,h=n-1;
	int m=0;
	while(l<=h){
		m = (l+h)/2;
		if(x == a[m]) return m;
		else if(x > a[m]) l = m+1;
		else h = m-1;
	}
	return -1;
}

/**
* 旋转数组中寻找指定的元素。
* 主要是根据中点m来判断两种不同的情况，然后再细分。
* 注意循环结束条件，以及l和h的更新。
*/
int searchRotateArray(int a[], int n, int x){
	int l = 0;
	int h = n-1;

	if(a == NULL) return -1;
	while(l+1 != h){	//当l的下一个位置就是h的时候就要结束

		int m = (l+h)/2;
		if(a[m] == x) return m;	//找到
		else if(a[m] >= a[l]){	//m落在左半部分
			if(x > a[m]) l = m;
			else{
				if(x > a[l]) h = m;
				else l = m;
			}
		}
		else{					//m落在又半部分
			if(x < a[m]) h = m;
			else{
				if(x < a[h]) l = m;
				else h = m;
			}
		}
	}
	return (a[l] == x)?l:-1;	//判断是否找到
}

int main(){
	int a[] = {0,1,2,3,4,4,4,5,8,9,10,11,12};
	int b[] = {1};
	int c[] = {9,10,11,12,2,3,4,4,5,6,7,8};
	int d[] = {1,1,1,1,0,0,1};
	
	cout<<binarySearch(a,13,2)<<endl;
	cout<<binarySearch2(b,1,1)<<endl;
	cout<<searchRotateArray(c,12,6)<<endl;;
	cout<<searchRotateArray(c,12,4)<<endl;
	cout<<searchRotateArray(a,13,2)<<endl;
	cout<<searchRotateArray(d,7,0)<<endl;
	cout<<searchRotateArray(c,7,-1)<<endl;
	cout<<searchRotateArray(d,7,3)<<endl;
	return 0;
}