算法设计与分析作业(一)实现几种不同情形的二分查找

 实现几种不同情形的二分查找。

 

1). 求等于x的最小的index，不存在返回-1。

输入:

3  5  5  7  7  10  11  12  

0  7  7

输出:

3

输入说明:

一组整形数组:3  5  5  7  7  10  11  12

查找的范围为:数组第0个元素至第7个元素

查找的元素为:7

 

2). 求等于x的最大的index，不存在返回-1。

输入:

3  5  5  7  7  10  11  12  

0  7  7

输出:

4

输入说明:

一组整形数组:3  5  5  7  7  10  11  12

查找的范围为:数组第0个元素至第7个元素

查找的元素为:7

 

3). 求小于x的最大的index。

输入:

3  5  5  7  7  10  11  12  

0  7  8

输出:

    4

输入说明:

一组整形数组:3  5  5  7  7  10  11  12

查找的范围为:数组第0个元素至第7个元素

查找的元素为:8

 

4). 求大于x的最小的index。

输入:

3  5  5  7  7  10  11  12  

0  7  6

输出:

3

输入说明:

一组整形数组:3  5  5  7  7  10  11  12

查找的范围为:数组第0个元素至第7个元素

查找的元素为:6

 

 

5). 求大于等于x的最小的index。

第一组输入:

3  5  5  7  7  10  11  12  

0  7  5

输出:

    1

输入说明:

一组整形数组:3  5  5  7  7  10  11  12

查找的范围为:数组第0个元素至第7个元素

查找的元素为:5

 

第二组输入:

3  5  5  7  7  10  11  12  

0  7  6

输出:

3

输入说明:

一组整形数组:3  5  5  7  7  10  11  12

查找的范围为:数组第0个元素至第7个元素

查找的元素为:6

 

 

6). 求小于等于x的最大的index。

第一组输入:

3  5  5  7  7  10  11  12   0  7  5

输出:

2

输入说明:

一组整形数组:3  5  5  7  7  10  11  12

查找的范围为:数组第0个元素至第7个元素

查找的元素为:5

 

第二组输入:

3  5  5  7  7  10  11  12   0  7  6

输出:

2

输入说明:

一组整形数组:3  5  5  7  7  10  11  12

查找的范围为:数组第0个元素至第7个元素

查找的元素为:6

 

    2. 编写一个实验程序，随机产生10个1~20的整数，设计一个高效算法找其中的最大的元素和最小的元素，并统计元素之间的比较次数。调用该算法执行10次并求元素的平均比较次数（运行时列出）。随机数生成在VC中可以使用库函数实现srand()、rand()，百度可查。

 

/*第一題二分查找*/
int binarysearch1(int a[],int low,int high,int target)
{
	int mid = (high + low) / 2;
	int record = -1;
	while(high>=low)
	{
		if(a[mid] < target)
			low = mid + 1;
		else if(a[mid] > target)
			high = mid - 1;
		else if(a[mid] == target){
			record = mid;
			high = mid - 1;
		}
		mid = (int)(high + low)/2;
	}
	return record;
}

/*第二題二分查找*/
int binarysearch2(int a[],int low,int high,int target)
{
	int mid = (high + low) / 2;
	int record = -1;
	while(high>=low)
	{
		if(a[mid] < target)
			low = mid + 1;
		else if(a[mid] > target)
			high = mid - 1;
		else if(a[mid] == target){
			record = mid;
			low = mid + 1;
		}
		mid = (int)(high + low)/2;
	}
	return record;
}

/*第三題二分查找*/
int binarysearch3(int a[],int low,int high,int target)
{
	int mid = (high + low) / 2;
	int record = -1;
	while(high>=low)
	{
		if(a[mid] < target){
			low = mid + 1;
			record = mid;
		}
		else if(a[mid] > target)
			high = mid - 1;
		else if(a[mid] == target)
			high = mid - 1;
		mid = (int)(high + low)/2;
	}
	return record;
}

/*第四題二分查找*/
int binarysearch4(int a[],int low,int high,int target)
{
	int mid = (high + low) / 2;
	int record = -1;
	while(high>=low)
	{
		if(a[mid] < target)
			low = mid + 1;
		else if(a[mid] > target){ 
			high = mid - 1;
			record = mid;
		}
		else if(a[mid] == target)
			low = mid + 1;
		mid = (int)(high + low)/2;
	}
	return record;
}

/*第五題二分查找*/
int binarysearch5(int a[],int low,int high,int target)
{
	int mid = (high + low) / 2;
	int record = -1;
	while(high>=low)
	{
		if(a[mid] < target)
			low = mid + 1;
		else if(a[mid] >= target){ 
			high = mid - 1;
			record = mid;
		}
		mid = (int)(high + low)/2;
	}
	return record;
}

/*第六題二分查找*/
int binarysearch6(int a[],int low,int high,int target)
{
	int mid = (high + low) / 2;
	int record = -1;
	while(high>=low)
	{
		if(a[mid] <= target){
			low = mid + 1;
			record = mid;
		}
		else if(a[mid] > target) 
			high = mid - 1;
		mid = (int)(high + low)/2;
	}
	return record;
}

/*
第七題
编写一个实验程序，随机产生10个1~20的整数
设计一个高效算法找其中的最大的元素和最小的元素，并统计元素之间的比较次数。
调用该算法执行10次并求元素的平均比较次数。
*/


#include<iostream>
#include<cstdlib>
using namespace std;

int binarycompareMax(int a[],int index_low,int index_high){
	int index_mid = (index_high + index_low) / 2;
	if(index_high > index_low){
		int r1 = binarycompareMax(a,index_low,index_mid);
		int r2 = binarycompareMax(a,index_mid+1,index_high);
		return r1>r2?r1:r2;
	}
	else if(index_high == index_low)
		return a[index_high];
	else{
		return 0;
	}
}

int main()
{
	int a[10];
	for(int i=0;i<10;i++)
		a[i] = rand();
	for(int i=0;i<10;i++)
		cout<<a[i]<<"  ";
	cout<<endl;
	cout<<binarycompareMax(a,0,9)<<endl;
	return 0;
}