二分查找的实现_C++

// 
 题目描述
1、定义一个顺序存储结构或者数组
2、主函数已经给出，提交代码不需要提交主函数
3、需要完成未给出的二分查找实现
4、中间处理：二分或折半查找，通过二分查找：理解查找成功的ASL和查找失败的ASL。
5、参考程序给出的输出实现二分查找


PS：本题考查二分查找，当然取巧的方式几行代码也能实现，不过不是我们推荐的方式。


int main()
{
    int iArray[MAX_SIZE] = {11,12,13,14,15,26,27,28,29,100};
    int iArrayAdd[MAX_SIZE] = {0};
    for(int i = 0; i < MAX_SIZE; i++)
    {
        iArrayAdd[i]= iArray[i]+1;
        int isearchRst = binarySearch(iArray, MAX_SIZE, iArrayAdd[i]);
        if(isearchRst != -1)
        {
            cout << iArrayAdd[i] << " is exist, location is " << isearchRst << endl;
        }
        else
        {
            cout << iArrayAdd[i] << " is not exist!" << endl;
        }
    }
}




输入
无 ，没有任何输入
输出
查找12第 1 次查找15
查找12第 2 次查找12
12共查找 2次！结果查找：成功！
12 is exist, location is 2
查找13第 1 次查找15
查找13第 2 次查找12
查找13第 3 次查找13
13共查找 3次！结果查找：成功！
13 is exist, location is 3
查找14第 1 次查找15
查找14第 2 次查找12
查找14第 3 次查找13
查找14第 4 次查找14
14共查找 4次！结果查找：成功！
14 is exist, location is 4
查找15第 1 次查找15
15共查找 1次！结果查找：成功！
15 is exist, location is 5
查找16第 1 次查找15
查找16第 2 次查找28
查找16第 3 次查找26
16共查找 3次！结果查找：失败！
16 is not exist!
查找27第 1 次查找15
查找27第 2 次查找28
查找27第 3 次查找26
查找27第 4 次查找27
27共查找 4次！结果查找：成功！
27 is exist, location is 7
查找28第 1 次查找15
查找28第 2 次查找28
28共查找 2次！结果查找：成功！
28 is exist, location is 8
查找29第 1 次查找15
查找29第 2 次查找28
查找29第 3 次查找29
29共查找 3次！结果查找：成功！
29 is exist, location is 9
查找30第 1 次查找15
查找30第 2 次查找28
查找30第 3 次查找29
查找30第 4 次查找100
30共查找 4次！结果查找：失败！
30 is not exist!
查找101第 1 次查找15
查找101第 2 次查找28
查找101第 3 次查找29
查找101第 4 次查找100
101共查找 4次！结果查找：失败！
101 is not exist!
样例输入 Copy

样例输出 Copy
查找12第 1 次查找15
查找12第 2 次查找12
12共查找 2次！结果查找：成功！
12 is exist, location is 2
查找13第 1 次查找15
查找13第 2 次查找12
查找13第 3 次查找13
13共查找 3次！结果查找：成功！
13 is exist, location is 3
查找14第 1 次查找15
查找14第 2 次查找12
查找14第 3 次查找13
查找14第 4 次查找14
14共查找 4次！结果查找：成功！
14 is exist, location is 4
查找15第 1 次查找15
15共查找 1次！结果查找：成功！
15 is exist, location is 5
查找16第 1 次查找15
查找16第 2 次查找28
查找16第 3 次查找26
16共查找 3次！结果查找：失败！
16 is not exist!
查找27第 1 次查找15
查找27第 2 次查找28
查找27第 3 次查找26
查找27第 4 次查找27
27共查找 4次！结果查找：成功！
27 is exist, location is 7
查找28第 1 次查找15
查找28第 2 次查找28
28共查找 2次！结果查找：成功！
28 is exist, location is 8
查找29第 1 次查找15
查找29第 2 次查找28
查找29第 3 次查找29
29共查找 3次！结果查找：成功！
29 is exist, location is 9
查找30第 1 次查找15
查找30第 2 次查找28
查找30第 3 次查找29
查找30第 4 次查找100
30共查找 4次！结果查找：失败！
30 is not exist!
查找101第 1 次查找15
查找101第 2 次查找28
查找101第 3 次查找29
查找101第 4 次查找100
101共查找 4次！结果查找：失败！
101 is not exist!

// 
#include<iostream>
using namespace std;
#define MAX_SIZE 10		//最大长度
typedef int KeyType;	//定义关键字类型为int

int binarySearch(int* pArray, int n, KeyType k) //折半查找算法
{
	int low = 0, high = n - 1, mid, chaci = 0;
	while (low <= high)			//当前区间存在元素时循环
	{
		chaci = chaci + 1;
		mid = (low + high) / 2;
		if (k == pArray[mid]) {		//查找成功返回其逻辑序号mid+1
			cout << "查找" << k << "第 " << chaci << " 次查找" << pArray[mid] << endl;
			cout << k << "共查找 " << chaci << "次！结果查找：成功！" << endl;
			return mid + 1;

		}
		else if (k < pArray[mid]) {	//继续在R[low..mid-1]中查找
			high = mid - 1;
			cout << "查找" << k << "第 " << chaci << " 次查找" << pArray[mid] << endl;
		}
		else {					//k>R[mid].key
			low = mid + 1;
			cout << "查找" << k << "第 " << chaci << " 次查找" << pArray[mid] << endl;
		}		//继续在R[mid+1..high]中查找
	}
	cout << k << "共查找 " << chaci << "次！结果查找：失败！" << endl;
	return -1;					//未找到时返回0（查找失败）
}