二分查找实现与分析-白红宇

二分查找实现与分析

阅读量：4136 次

发布时间：2019-05-25

本文共 3863 字，大约阅读时间需要 12 分钟。

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

#include "stdafx.h"#include 
   
    #include 
    
     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

分析与解法：

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

程序的第一个问题就是：midIndex=(minIndex+maxIndex)/2;这样的写法粗看没什么不妥，但是在一些极端情况下，会由于求和中间结果的溢出而导致出现错误(假设这是个32位程序，32位有符号整数可以表示的范围是-2³¹~2³¹-1，如果minIndex+maxIndex的值恰好超过了2³¹-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 
   
    #include 
    
     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

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

给定一个有序(不降序)数组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 
   
    #include
    
     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 -1;	while(end-begin>1)	{		mid=begin+(end-begin)/2;		if(a[mid]>v)		{			end=mid;		}		else if(a[mid]
      
       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]
       
        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"<
        
         <

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

转载地址：http://wjsvi.baihongyu.com/

你可能感兴趣的文章