折半查找（二分）

zk126 / 2023-05-10 / 原文

一、问题描述

　　N个有序整数数列已放在一维数组中，利用二分查找法查找整数m在数组中的位置。若找到，则输出其下标值:反之，则输出“Not be found!"。

二、问题分析

　　二分查找法(也叫折半查找)其本质是分治算法的一种。所谓分治算法是指的分而治之，即将较大规模的问题分解成几个较小规模的问题，这些子问题互相独立且与原问题相同，通过对较小规模问题的求解达到对整个问题的求解。我们把将问题分解成两个较小问题求解的分治方法称为二分法。需要注意的是，二分查找法只适用于有序序列。
　　二分查找的基本思想是:每次查找前先确定数组中待查的范围，假设指针low和high(low<high)分别指示待查范围的下界和上界，指针mid指示区间的中间位置，即mid=(low+high) /2,把m与中间位置(mid)中元素的值进行比较。如果m的值大于中间位置元素中的值，则下-次的查找范围放在中间位置之后的元素中:反之，下一次的查找范围放在中间位置之前的元素中享到orwtigh, 查找结束。

三、二分算法的适用范围

　　二分算法可以快速的寻找一个序列种的边界值，那何为边界值呢。

对于一个有序的序列来说，我们可以将这个数列以一个数n为边界，这个数的左边所有数满足一个性质（比如说小于n），这个数的右边所有数则满足另外一个性子（比如说大于等于n），此时我们则可以用二分对这个n进行快速查找。

注意：二分一定是有解的，但是对于一个题目来说，题目可能无解（即二分出来的结果并不是你想要找的那个数）。

四、代码实现：

#include<iostream>
using namespace std;
int main()
{
    int a[10] = { -3,4,7,9,13,45,67,89,100,180 };
    int l = 0, r = 9, m;
    cin >> m;
    while (l < r)
    {
        int mid = l + r >> 1;
        if (a[mid] >= m) r = mid;
        else l = mid + 1;
    }
    if (a[l] == m) cout << l << endl;
    else cout << "Not be found!" << endl;
    return 0;
}