博客主页 🏗️
折半查找(二分查找)
折半查找(二分查找)

Author:

wy-1226

©

Wordage:

共计 1706 字

needs:

约 1 分钟

Popular:

199 ℃

Created:

目 录

考研时需要学习的一个算法,这里手打实现一个简单的折半查找

折半查找(二分查找)

介绍

折半查找法是效率较高的一种查找方法。假设有已经按照从小到大的顺序排列好的五个整数a0~a4,要查找的数是X,其基本思想是: 设查找数据的范围下限为l=0,上限为h=4,求中点m=(l+h)/2,用X与中点元素am比较,若X等于am,即找到,停止查找;否则,若X大于am,替换下限l=m+1,到下半段继续查找;若X小于am,换上限h=m-1,到上半段继续查找;如此重复前面的过程直到找到或者l>h为止。如果l>h,说明没有此数,打印找不到信息,程序结束。

实现

递归

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int a[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};


//vector<int> array;

int BineraySearch(int* a,int left,int right,int target)//返回所在下标 
{
    if(left>right)
        return -1;
    int mid = (right - left) / 2 + left;
    cout<<left<<" "<<mid<<" "<<right<<endl;
    if(a[mid]<target)
    {
        left = mid + 1;
    }
    else if(a[mid]>target)
    {
        right = mid - 1;
    }
    else
    {
        return mid;
    }

    BineraySearch(a,left,right,target);
    
}


int main()
{

    int target=0;
    cin >> target;

    cout<<BineraySearch(a,1,10,target);
    return 0;
}

非递归

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int a[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int main()
{

    int target=0;
    cin >> target;

//    cout<<BineraySearch(a,1,10,target);
    int left=0;
    int right=9;
    while(left<=right)
    {
        int mid = (right - left) / 2 + left;
        cout<<left<<" "<<mid<<" "<<right<<endl;
        if(a[mid]<target)
        {
            left = mid + 1;
        }
        else if(a[mid]>target)
        {
            right = mid - 1;
        }
        else
        {
             cout<<mid<<endl;
             break;
        }
    }
    if(left>right)
        cout<<"Failed"!<<endl;
    return 0;
}
文章二维码
折半查找(二分查找)
共计 0 条评论,点此发表评论
博客主页 wyのblog I know you are here. 百度统计
鄂ICP备2023003777号-1 本站已运行 324 天 13 小时 2 分 自豪地使用 Typecho 建站,并搭配 MyDiary 主题 Copyright © 2023 ~ 2024. wyのblog All rights reserved.
打赏图
打赏博主
欢迎
搜 索
足 迹
分 类
  • 默认分类
  • Code
  • 日记
  • 音乐
  • 游戏
  • 阅读
  • 计划
  • 图片
  • 旅游
  • 影视