【分治法】两分查找

叁歲伎倆 2022-04-18 02:16 216阅读 0赞

问题描述：

已知一个数组为升序，给定一个值，在此数组中查找是否存在，是则返回下标，否则提示“not found”.

解1：思维上最先想到的是顺序查找，即线性查找，对数组做遍历；思维上简单，然其耗时较长。这个的时间复杂度为cita(n);

解2：两分查找：类似于查字典，过程如下：

1.   确定查找范围后，定义binary=n/2；
2.  若x等于a\[binary\],返回binary，结束；
3.  若x小于a\[binary\]，就去前面部分查找，回到第一步；
4.  若x大于a\[binary\],   就到后面部分查找，返回第一步。

关键在于如何用分治法做循环，循环到什么时候停止（找到的条件、找不到的条件）；

代码如下：

#include<iostream>
    #include<cstring>
    using namespace std;
    int searchBy(int data[],int n,int x)
    {
        int low=0;
        int high=n-1;
        int binary=(low+high)/2;
        while(x!=data[binary]&&low<=high)     //循环的条件就是x不等于中间数且低位置小于高位置
        {
            if(x<data[binary])
                high=binary-1;
            else
                low=binary+1;
            binary=(high+low)/2;
        }
        if(low<=high)
            return binary;
        else
            return -1;
    }
    int main ()
    {
        int n;
        int a[10]={9,19,29,39,49,59,69,79,89,99};
        cout<<"please input a number:"<<endl;
        cin>>n;
        int i=searchBy(a,10,n);
        for(int i=0;i<10;i++)
            cout<<a[i]<<" ";
        cout<<endl;
        if(i==-1)
            cout<<"Not found!"<<endl;
        else
            cout<<"founded at "<<i+1<<endl;
    
    }

这种两分查找的时间复杂度为  T(n)=cita（lgn）;较之方法一，在大的数据下有明显优势。

发表评论取消回复

表情：

评论列表（有 0 条评论，216人围观）

还没有评论，来说两句吧...

相关阅读

相关 C语言实现：折半查找算法（递归、分治法）

C语言实现：折半查找算法（递归）（分治法）文章目录 C语言实现：折半查找算法（递归）（分治法） 1. 问题 2. 解决方案

一时失言乱红尘/ 2024年03月31日 16:15/ 0 赞/ 59 阅读

相关棋盘覆盖--分治法

问题：在一个2^k×2^k （k≥0）个方格组成的棋盘中，恰有一个方格与其他方格不同，称该方格为特殊方格。显然，特殊方格在棋盘中可能出现的位置有4^k种，因而有4^k种不同

柔情只为你懂/ 2024年02月18日 16:10/ 0 赞/ 41 阅读

相关分治法-归并排序

一、前言归并排序归并排序是建立在归并操作上的一种有效的排序算法，速度仅次于快速排序，为稳定排序算法，一般用于对总体无序，但是各子项相对有序的数列。该算法是采用分

落日映苍穹つ/ 2022年11月16日 05:47/ 0 赞/ 193 阅读

相关 Python|分治（分而治之）法

本文首发于微信公众号："算法与编程之美"，欢迎关注，及时了解更多此系列文章。前言分治思想自古就有，在《孙子兵法》中有这么一句话：凡治众如治寡，分数是也：斗众如斗寡，

向右看齐/ 2022年10月12日 01:55/ 0 赞/ 171 阅读

相关分治法

问题描述:假定一个已经排好顺序的一维数组,运用二分搜索算法,使得当前输入元素x不在数组中是，返回小于x的最大元素位置i和大于x的最小元素的位置j,当搜索元素在数组中，i 和j

怼烎@/ 2022年06月03日 05:52/ 0 赞/ 247 阅读

相关【分治法】两分查找

问题描述：已知一个数组为升序，给定一个值，在此数组中查找是否存在，是则返回下标，否则提示“not found”. 解1：思维上最先想到的是顺序查找，即线性查找，对数组做遍

叁歲伎倆/ 2022年04月18日 02:16/ 0 赞/ 217 阅读

相关分治法

Problem1一元三次方程的解题目描述有形如：ax3+bx2+cx+d=0这样的一个一元三次方程。给出该方程中各项的系数(a，b，c，d均为实数)，并约定该方程存在三

╰半夏微凉°/ 2022年01月06日 22:11/ 0 赞/ 281 阅读

相关分治法简介

简介对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，[递归][L

r囧r小猫/ 2021年11月23日 06:30/ 0 赞/ 352 阅读

相关分治算法 ------二分查找

https://www.youtube.com/watch?v=EMw1rwQmD3w&index=27&list=PLvdLBjhf\_tgqq0ESrSd4rH8bXLmO

Love The Way You Lie/ 2021年11月10日 02:32/ 0 赞/ 273 阅读

相关分治法——归并排序

归并排序归并排序是成功应用分治法的完美例子，归并排序是按照记录在序列中的位置对序列进行划分。【问题】应用归并排序方法对一个记录序列进行升序排序。归并排序（m

￡神魔★判官ぃ/ 2021年06月22日 15:36/ 0 赞/ 479 阅读