二分查找之变型题目

二分查找算法在各个公司的笔试面试题大量出现，通常不是简单一眼就可以看出来的二分查找。
我见过的一些变型，一种是有序的环形队列，不知道队头，另一种是有序数组循环移动得到的数组，这种变型无非是多绕了一个弯，多一次查找，首先二分查找到队头，最小元素/最大元素，然后再二分查找指定的元素。

#include <iostream>
#include <cstdlib>

/*
 * Author: fuliang http://fuliang.iteye.com
 * 二分查找分界点，最小值的index
 */
int binary_search_min(int a[],int n){
	if(n <= 0) return -1;
	if(a[0] < a[n-1]) return 0;//递增有序序列
	int b = a[0];
	int i = 0,j = n-1;
	int mid;
	while(i < j){
		mid = (i  + j) / 2;
		if( a[mid] >= b ){
			i = mid+1;
		}else {
			j = mid;
			b = a[mid];
		}
	}
	return i;
}

int cmp(const void *x, const void *y){
	 return ( *(int *)x - *(int*)y );
}
/*
 * 根据分界点二分查找
 */
int * bin_search(int x,int a[],int n,int m_index){
	if(a[n-1] >= x){
		return (int *)bsearch(&x,a+m_index,n-m_index,sizeof(int),cmp) ;
	}else{
		return (int *)bsearch(&x,a,m_index,sizeof(int),cmp) ;
	}
}

int main(){
	int a[] = {4,5,6,7,8,1,2,3};
	int m_index = binary_search_min(a,8);
	int *target_addr = bin_search(6,a,8,m_index) ;
	if(target_addr){
		std::cout << "Min index: " << m_index << " and result index: " << target_addr - a << std::endl;
	}else{
		std::cout  << "Not find" << std::endl;
	}
}