二分查找实现与分析

本是古典何须时尚 2021-06-24 16:09 325阅读 0赞

首先先看下如下二分查找的代码：

#include "stdafx.h"
    #include <stdio.h>
    #include <string.h>
    int BinarySearch(const char **arr,int minIndex,int maxIndex,const char *value);
    int _tmain(int argc, _TCHAR* argv[])
    {
    	const char *cArr[] = {"ab", "abc", "abcd", "abcde", "abcde"};
    	const char *v = "abcd";
    	int index=BinarySearch(cArr,0,4,v);
    	printf("%s\n",cArr[index]);
    
    	return 0;
    }
    int BinarySearch(const char **arr,int minIndex,int maxIndex,const char *value)
    {
    	while (minIndex<maxIndex)
    	{
    		int midIndex=(minIndex+maxIndex)/2;
    		if (strcmp(arr[midIndex],value)<0)
    			minIndex=midIndex+1;
    		else if (strcmp(arr[midIndex],value)==0)
    			return midIndex;
    		else
    			maxIndex=midIndex-1;
    	}
    
    	if (strcmp(arr[minIndex],value)==0)
    		return minIndex;
    	else if(strcmp(arr[maxIndex],value)==0)
    		return maxIndex;
    	else
    		return -1;
    }

分析与解法：

在写循环或递归的时候，我们应该特别注意三个方面的问题：初始条件、转化和终止条件。针对上面这个二分程序，我们也要逐一考虑这些方面。

程序的第一个问题就是：midIndex=(minIndex+maxIndex)/2;这样的写法粗看没什么不妥，但是在一些极端情况下，会由于求和中间结果的溢出而导致出现错误(假设这是个32位程序，32位有符号整数可以表示的范围是-231~231\-1，如果minIndex+maxIndex的值恰好超过了231\-1，那么就会造成上溢出，导致midIndex变成负数)。所以我们最好把它写成midIndex=minIndex +( maxIndex-minIndex)/2。

程序的第二个问题就是：循环的终止条件可能无法到达，也就是说，在某些测试用例下，程序不会停止。当minIndex=2，maxIndex=3且arr\[minIndex\]<=v的时候，程序将进入死循环。

注意：intstrcmp(const char \*s1,const char \* s2);因此在int BinarySearch(constchar \*\*arr,int minIndex,int maxIndex,const char \*value);中，参数arr为常量且是指针的指针，这样才能符合strcmp函数参数的要求。

所以修改后的代码如下所示：

#include "stdafx.h"
    #include <stdio.h>
    #include <string.h>
    int BinarySearch(const char **arr,int minIndex,int maxIndex,const char *value);
    int _tmain(int argc, _TCHAR* argv[])
    {
    	const char *cArr[] = {"ab", "abc", "abcd", "abcde", "abcde"};
    	const char *v = "abcdt";
    	int index=BinarySearch(cArr,0,4,v);
    	if (index!=-1)
    		printf("%s\n",cArr[index]);
    	else
    		printf("No data!\n");
    
    	return 0;
    }
    int BinarySearch(const char **arr,int minIndex,int maxIndex,const char *value)
    {
    	while (minIndex<maxIndex-1)//等价于minIndex<=maxIndex，但就是不能为minIndex<maxIndex
    	{
    		int midIndex=minIndex+(maxIndex-minIndex)/2;//防止数字范围溢出
    		if (strcmp(arr[midIndex],value)<0)
    			minIndex=midIndex+1;
    		else if (strcmp(arr[midIndex],value)==0)
    			return midIndex;
    		else
    			maxIndex=midIndex-1;
    	}
       return -1;
    }

关于这个二分查找，有些类似的相关题型：

给定一个有序(不降序)数组arr，求任意一个i使得arr\[i\]等于v，不存在返回-1.

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

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

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

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

可以思考下，以上几个题的答案代码如何写。

//============================================================================
    // Name        : 编程之美程序改错.cpp
    // Author      :
    // Version     :
    // Copyright   : Your copyright notice
    // Description : Hello World in C++, Ansi-style
    //============================================================================
    
    #include <iostream>
    #include<stdlib.h>
    using namespace std;
    int findValue(int *a,int begin,int end,int v)
    {
    	int mid;
    	while(begin<=end)
    	{
    		mid=begin+(end-begin)/2;
    		if(a[mid]==v)
    			return mid;
    		if(a[mid]>v)
    		{
    			end=mid-1;
    		}
    		else
    			begin=mid+1;
    	}
    	return -1;
    
    }
    
    int findMinValue(int *a,int begin,int end,int v)
    {
    	int mid;
    	int begin1=begin;
    	while(begin<=end)
    	{
    		mid=begin+(end-begin)/2;
    		if(a[mid]==v)
    			break;
    		if(a[mid]>v)
    		{
    			end=mid-1;
    		}
    		else
    			begin=mid+1;
    	}
    
    	if(begin>end)
    		return -1;
    
    	if(mid-1>=begin1&&a[mid-1]==v)
    		mid--;
    	return mid;
    }
    
    int findMaxValue(int *a,int begin,int end,int v)
    {
    	int mid;
    	int length=end;
    	while(begin<=end)
    	{
    		mid=begin+(end-begin)/2;
    		if(a[mid]==v)
    			break;
    		if(a[mid]>v)
    		{
    			end=mid-1;
    		}
    		else
    			begin=mid+1;
    	}
    
    	if(begin>end)
    		return -1;
    
    	if(mid+1<=length&&a[mid+1]==v)
    		mid++;
    	return mid;
    }
    
    int findMaxiValue(int *a,int begin,int end,int v)
    {
    	int mid;
    	if(a[end]<v)
    		return end;
    	if(a[begin]>=v)
    		return -1;
    
    	while(end-begin>1)
    	{
    		mid=begin+(end-begin)/2;
    		if(a[mid]>v)
    		{
    			end=mid;
    		}
    		else if(a[mid]<v)
    			begin=mid;
    		else if(a[mid]==v)
    			break;
    	}
    
        if(end-begin>1)
        {
        	if(mid-1>0&&a[mid-1]==v)
        		mid--;
        	mid--;
        	return mid;
        }
    	return begin;
    }
    
    int findMiniValue(int *a,int begin,int end,int v)
    {
    	int mid;
    	if(a[end]<=v)
    		return -1;
    	if(a[begin]>v)
    		return begin;
    
    	while(end-begin>1)
    	{
    		mid=begin+(end-begin)/2;
    		if(a[mid]>v)
    		{
    			end=mid;
    		}
    		else if(a[mid]<v)
    			begin=mid;
    		else if(a[mid]==v)
    			break;
    	}
    
        if(end-begin>1)
        {
        	if(mid+1>0&&a[mid+1]==v)
        		mid++;
        	mid++;
        	return mid;
        }
    	return end;
    }
    
    int brsearch(char **arr,int begin,int end,char *v)
    {
    	int mid;
    	while(begin<=end)
    	{
    		mid=begin+(end-begin)/2;
    		if(strcmp(arr[mid],v)>0)
    		{
    			end=mid-1;
    		}
    		else if(strcmp(arr[mid],v)<0)
    		{
    			begin=mid+1;
    		}
    		else if(!strcmp(arr[mid],v))
    		{
    			break;
    		}
    	}
    
    	if(begin>end)
    		throw new string("no v");
    	cout<<"mid is"<<mid<<endl;
    	while(mid+1<=end&&!strcmp(arr[mid+1],v))
    		mid++;
    	return mid;
    }
    
    int main() {
    	char **a=new char*[10];
    	a[0]=new char[10];
    	a[0]="hello";
    	a[1]=new char[10];
    	a[1]="yello";
    	a[2]=new char[10];
    	a[2]="yello";
    	a[3]=new char[10];
    	a[3]="zebra";
    
    	char v[10]="zebra";
    	cout<< brsearch(a,0,3,v)<<endl;
    
    	int a1[20]={1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9,11,11};
    	cout<<findValue(a1,0,18,11)<<endl;
    	cout<<findMinValue(a1,0,18,9)<<endl;
    	cout<<findMaxValue(a1,0,18,19)<<endl;
    	cout<<findMaxiValue(a1,0,18,10)<<endl;
    	cout<<findMiniValue(a1,0,18,8)<<endl;
    
    
    
    	return 0;
    }

以上内容参考《编程之美》第3.11节的内容。