DS静态查找之折半查找

叶茂林

发布于 2023-07-30 13:29:05

3020

文章被收录于专栏：叶子的开发者社区叶子的开发者社区

题目描述

给出一个队列和要查找的数值，找出数值在队列中的位置，队列位置从1开始

要求使用折半查找算法

输入

第一行输入n，表示队列有n个数据第二行输入n个数据，都是正整数，用空格隔开第三行输入t，表示有t个要查找的数值第四行起，输入t个数值，输入t行

输出

每行输出一个要查找的数值在队列的位置，如果查找不成功，输出字符串error

输入样例1

8 11 22 33 44 55 66 77 88 3 22 88 99

输出样例1

2 8 error

思路分析

折半查找就是二分查找，，对于一个有序数列，通过三个位置的变换（low、mid、high），相当于部分顺序查找，只不过每次把查找的范围缩小一半。

开始先让low=0，high=n-1，mid=n/2，如果要查找的数值比mid位置的大，那么说明数值有可能在mid和high之间，那么就让low=mid+1，mid=（low+high）/2，继续查找下去，如果比mid位置的小，那么说明数值有可能在low和mid之间，那么就让high=mid-1，mid=（low+high）/2，继续查找下去，直到mid位置上的就是要查找的数值，或者low>high，查找结束。

AC代码

#include <iostream>
using namespace std;
int main() {
    int n,t,target;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++)
        cin>>a[i];
    cin>>t;
    while(t--){
        cin>>target;
        int low=0,high=n-1,mid=n/2;
        while(low<=high){
            if(a[mid]==target){
                cout<<mid+1<<endl;
                break;
            }else if(a[mid]<target){
                low=mid+1;
                mid=(low+high)/2;
            }else{
                high=mid-1;
                mid=(low+high)/2;
            }
        }
        if(low>high)
            cout<<"error"<<endl;
    }
    return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2022-12-05，如有侵权请联系 cloudcommunity@tencent.com 删除

int