C++二分查找

一、介绍：

二分查找又称折半查找，是一种相比较顺序查找效率较高的查找方法。但是，二分查找要求线性表中的记录必须采用顺序存储。

二、比较演示： 

 三、方法：

        （1）设置查找区间：

1.  
   int left;// C 自动初始化为0
2.  
   int right=n;

        （2）若查找区间不存在，则查找失败，返回；否则执行（3）。

        （3）取中间位，比较与 ，有三种情况：

                1. 若 x < a[mid]，则right = mid - 1；查找在左半区间进行，转（2）；

                2. 若 x > a[mid]，则left = mid 1；查找在右半区间进行，转（2）；

                3. 若 x = a[mid]，则查找成功，返回mid的值；

 四、时间复杂度比较：

        （1）顺序查找：

                1.最好时间复杂度：

                        

                2.最坏时间复杂度：

                        

        （2）二分查找：

                1.最好时间复杂度：

                        

                2. 最坏时间复杂度：

                        

 五、代码部分：

1.  
   #include<iostream>
2.  
   using namespace std;
3.  
   int n, x, a[105];
4.  
   int bs(int left, int right, int x) {
5.  
   int mid = (left right) / 2;
6.  
   if (x < a[mid]) {
7.  
   return bs(left, mid - 1, x);
8.  
   }
9.  
   else if (x > a[mid]) {
10.  
    return bs(mid 1, right, x);
11.  
    }
12.  
    else {
13.  
    return mid;
14.  
    }
15.  
    }
16.  
    int main() {
17.  
    cin >> n >> x;
18.  
    for (int i = 0; i < n; i ) {
19.  
    cin >> a[i];
20.  
    }
21.  
    cout << bs(0, n, x);
22.  
    return 0;
23.  
    }

如果这篇文章对你有帮助的话，记得点个赞和收藏再走啊 ！！！

这篇好文章是转载于：学新通技术网