菜鸟笔记
提升您的技术认知

二分查找的实现


题目描述

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!

样例输入

样例输出

查找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;

const int MAX_SIZE = 10;


int binarySearch(int R[], int n, int k)
{
  
    int low = 0;
    int high = n - 1;
    int mid;
    int i = 0;
    while(low <= high)
    {
  

        mid = (low + high)/2;
        cout<<"查找"<<k<<"第 "<<++i<<" 次查找"<<R[mid]<<endl;
        if(k == R[mid])
        {
  
            cout<< k <<"共查找 "<< i <<"次!结果查找:成功!"<<endl;
            return mid +1;
        }
        if(k < R[mid])
        {
  
            high = mid - 1;
        }
        else
        {
  
            low = mid + 1;
        }

    }

    cout<< k <<"共查找 "<< i <<"次!结果查找:失败!"<<endl;
    return -1;
}

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;
        }
    }
}