编程之美 3.11二分查找系列

题目1：找出一个有序字符串数组arr中值等于字符串v的元素的序号，如果有多个元素满足这个条件，返回序号最大的

这里和最基本的二分查找不一样的地方，二分查找，找到一个就可以返回，这里找到了还得继续往后走，找最大的

int bisearch(char** arr,int b, int e, char* v)
{
	int minindex = b,maxindex = e,midindex;
	while (minindex < maxindex -1 ) //如果是midinex < maxindex，对于连续的两个如0 1，则会导致死循环
	{
		midindex = minindex + (maxindex - minindex)/2;//防止minindex + maxindex溢出
		if(strcmp(arr[midindex],v)<=0)
			minindex = midindex;//因为存在可能相等的情况，所以不能+1
		else
			maxindex = midindex;
	}
	//退出循环，可能和minindex相等，也可能和maxindex相等，所以两者都需要进行比较
	if(!strcmp(arr[maxindex],v))
		return maxindex;
	else if(!strcmp(arr[minindex],v))
		return minindex;
	else
		return -1;
}
           

拓展题目：

①给定一个有序（不降序）数组arr，求任意一个i使得arr[i]等于v，不存在则返回-1

int bisearch(int arr[], int begin, int end, int value) 
{
	while (begin<=end)
	{
		int mid = begin + (end -begin)/2;
		if(arr[mid]==value)
			return mid;
		else if(arr[mid]>value)
			end = mid -1;
		else
			begin = mid +1;
	}
	return -1;
}
           

②给定一个有序（不降序）数组arr，求最小的i使得arr[i]等于v，不存在返回-1

思路：要求最小的，则mid相等的话，还不能直接返回，循环结束的条件也不一样，此时相等时，minindex不能再移动，只有明确<小于时，才能移动   退出循环后的判断 先小后大

int bisearch(char** arr,int b, int e, char* v)
{
	int minindex = b,maxindex = e,midindex;
	while (minindex < maxindex -1 ) //如果是midinex < maxindex，对于连续的两个如0 1，则会导致死循环
	{
		midindex = minindex + (maxindex - minindex)/2;//防止minindex + maxindex溢出
		if(strcmp(arr[midindex],v)<0)</span>
			minindex = midindex;//因为存在可能相等的情况，所以不能+1
		else
			maxindex = midindex;
	}
	//退出循环，可能和minindex相等，也可能和maxindex相等，所以两者都需要进行比较
	if(!strcmp(arr[minindex],v))
		return minindex;
	else if(!strcmp(arr[maxindex],v))
		return maxindex;</span>
	else
		return -1;
}
           

③给定一个有序（不降序）数组arr，求最大的i使得arr[i]等于v，不存在返回-1

思路：退出循环后的判断，先大后小

int bisearch(char** arr,int b, int e, char* v)
{
	int minindex = b,maxindex = e,midindex;
	while (minindex < maxindex -1 ) //如果是midinex < maxindex，对于连续的两个如0 1，则会导致死循环
	{
		midindex = minindex + (maxindex - minindex)/2;//防止minindex + maxindex溢出
		if(strcmp(arr[midindex],v)<=0)</span>
			minindex = midindex;//因为存在可能相等的情况，所以不能+1
		else
			maxindex = midindex;
	}
	//退出循环，可能和minindex相等，也可能和maxindex相等，所以两者都需要进行比较
	if(!strcmp(arr[maxindex],v))
		return maxindex;
	else if(!strcmp(arr[minindex],v))
		return minindex;</span>
	else
		return -1;
}
           

④ 给定一个有序（不降序）数组arr，求最大的i使得arr[i]小于v，不存在返回-1

int bisearch(char** arr,int b, int e, char* v)
{
	int minindex = b,maxindex = e,midindex;
	while (minindex < maxindex -1 ) //如果是midinex < maxindex，对于连续的两个如0 1，则会导致死循环
	{
		midindex = minindex + (maxindex - minindex)/2;//防止minindex + maxindex溢出
		if(strcmp(arr[midindex],v)<0)
			minindex = midindex;
		else
			maxindex = midindex;
	}
	//退出循环，可能和minindex相等，也可能和maxindex相等，所以两者都需要进行比较
	if(strcmp(arr[maxindex],v)<0)
		return maxindex;
	else if(strcmp(arr[minindex],v)<0)
		return minindex;
	else
		return -1;
}
           

⑤ 给定一个有序（不降序）数组arr，求最小的i使得arr[i]大于v，不存在返回-1

int bisearch(char** arr,int b, int e, char* v)
{
	int minindex = b,maxindex = e,midindex;
	while (minindex < maxindex -1 ) //如果是midinex < maxindex，对于连续的两个如0 1，则会导致死循环
	{
		midindex = minindex + (maxindex - minindex)/2;//防止minindex + maxindex溢出
		if(strcmp(arr[midindex],v)<=0)
			minindex = midindex;
		else
			maxindex = midindex;
	}
	//退出循环，可能和minindex相等，也可能和maxindex相等，所以两者都需要进行比较
	if(strcmp(arr[minindex],v)>0)
		return minindex;
	else if(strcmp(arr[maxindex],v)>0)
		return maxindex;
	else
		return -1;
}