算法06 二分查找

二分查找的概念

二分查找又称为折半查找，主要用于查找一个有序数组中某一个数的位置。

主要思想如下：

在一个有序数组中，取数组的中间值与要查找的数进行比较；

若要查找的数等于中间值，查找成功。

二分查找的步骤

若要查找的数大于中间值，则在右半区间继续取中间值与要查找的数进行比较；

若要查找的数小于中间值，则在左半区间继续取中间值与要查找的数进行比较；

直至最后要查找的数未出现过与中间值相等的情况，查找失败

二分查找

使用自定义函数的方法，需要引入的三个参数分别是整个数组，数组长度，查找值。返回的是查找值在数组中的位置。

int Search(int a[],int n,int key){
    int low = 1;//左边界从1开始
    int high = n;//右边界从n开始
    while(low <= high) {
        int mid = low + ((high-low)/2);
                //中间下标
        if(key == a[mid])
                //相等代表找到
            return mid;
         else if(key < a[mid])
          //比中间小，把右边界缩小
            high = mid - 1;
         else//比中间大，把左边界缩小
            low = mid + 1;
    }
    return -1;//如果都找不到
}

二分查找的优势

二分查找因为每次查找都会把这个数据折半，所以效率相对较高。如果使用普通的查找可能会消耗太多的时间。

大家可以试试看，在1-100之间随便设定一个数字，只需要最多最多7次肯定能猜对，每次问的都是这个数字和范围中间的数字比大小，每次比完都能去掉一半的数字。

找某个数的位置

在有序数组中查找某个数，找到返回数的下标，不存在重复的值，没有返回-1。

【输入描述】第一行两个整数空格分开，分别表示序列长度n以及查询次数m。

第二行输入n个整数

接下来m行，每行一个整数，表示查询的数字。

【输出描述】输出m行，每行为查询数字的位置（位置从1开始算）。

【样例输入】3 3

4 6 9

9

4

7

【样例输出】3

1

-1

参考代码

#include<iostream>
using namespace std;
int Search(int a[] , int n, int key){
    int low = 1;
    int high = n;
    while(low <= high) {
        int mid = low + ((high-low)/2);
        if(key == a[mid])   return mid;
        else if(key < a[mid])high = mid - 1;
        else low = mid + 1;
    }
    return -1;
}
int main()
{
    int s[100000],n,m,b;
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>s[i];
    for(int i=1;i<=m;i++)
    {
        cin>>b;
        cout<<Search(s,n,b)<<endl;
    }
    return 0;
}

查找第一个比某数大的数

从一个有序的整数序列中查找第一个大于整数k的数，如果存在输出出现位置，否则输出-1。序列有重复元素，并且单调递增。

【输入描述】第一行两个整数空格分开，分别表示序列长度n以及查询次数m。

第二行输入n个整数

接下来m行，每行一个整数，表示查询的数字

【输出描述】输出m行，每行为查询数字的位置（位置从1开始算）。

【样例输入】

5 3

2 2 3 3 5

3

2

6

【样例输出】

5

3

-1

参考代码

int Search(int a[] , int n, int key){
    int low = 1;
    int high = n;
    while(low <= high) {
        int mid = low + ((high-low)/2);
        if(key < a[mid])high = mid - 1;
        else low = mid + 1;//相等的情况
    }
    if(low<=n)return low;
    //判断左边界是否超过最后一个数
    else return -1;
}