二分查找与判定树

这篇具有很好参考价值的文章主要介绍了二分查找与判定树。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

二分查找的算法思想

二分查找也称“折半查找”,要求查找表为采用顺序存储结构有序表。本例一律采用升序排列。二分查找每一次都会比较给定值与序列[low,high]的中间元素,该元素的下标为mid = (low+high)/2,若两者相等,则返回元素的下标为mid;如果arr[mid]>key,说明给定值key在中间元素的左边,此时只需要查找序列[low,mid-1]的中间元素;如果arr[mid]<key,说明给定值key在中间元素的右边,此时只需要查找序列[mid+1,high]。由于每一次比较arr[mid]与key失败都只需要查找剩下序列的一半,故谓之'二分查找'。显而易见,二分查找适合使用递归实现,递归的终止条件为low>high。

代码实现

注意了哈,此处的查找下标从1开始,下标0已经被弃用。

#include<iostream>
using namespace std;

int arr[10] = { 0,1,3,5,12,32,42,53,56,89};
//非递归实现
int Search_Bin(const int key) {
    //最左边的下标从1开始
    int low = 1, high = 10;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (arr[mid] == key) {
            return mid;
        }
        else if (arr[mid] < key) {
            low = mid + 1;
        }
        else {
            high = mid - 1;
        }
    }
    return -1;    
}

//递归实现
int Search_Bin(const int key, int low, int high) {
    if (low > high) {
        return -1;
    }
    int mid = (low + high) / 2;
    if (arr[mid] == key)    
        return  mid;
    else if (arr[mid] > key)  
        return Search_Bin(key, low, mid - 1);
    else 
        return Search_Bin(key, mid+1, high);
}

void test01() {
    cout << "----调用非递归函数------" << endl;
    cout << "ret = 1的下标为" << Search_Bin(1) << endl;
    cout << "ret = 43的下标为" << Search_Bin(43) << endl;
    cout << "ret = 100的下标为" << Search_Bin(100) << endl;

    cout << "----调用递归函数---------" << endl;
    int len = sizeof(arr) / sizeof(int);
    cout << "ret = 1的下标为" << Search_Bin(1,1,len) << endl;
    cout << "ret = 43的下标为" << Search_Bin(43, 1, len) << endl;
    cout << "ret = 100的下标为" << Search_Bin(100, 1, len) << endl;
}

int main() {
    test01();
    return 0;
}
二分查找与判定树

二分查找的判定树

二分查找的过程可以用一棵二叉树来描述,若用二叉树构造序列[low,high]的判定树,那么二叉树的根结点的存储值为序列[low,high]的中间元素的位置mid,而二叉树的左子树构造序列[low,mid-1]的判定树,右子树构造序列[mid+1,high]的判定树。查找给定值key的过程,就是逐一自上而下遍历二叉树根结点的过程。

查找次数不会超过二叉树的深度,假设序列有n个元素,那么查找的次数:count<=[log(2)n]+1。以下构造序列[1,10]的判定树,如图所示,查找的第一个下标必定为5,如果key值较arr[5]小,那么第二个查找的下标必定为2,否则为8。总而言之,倘若查找成功,查找下标的顺序就是二叉树的遍历顺序。

二分查找与判定树

由于判定树的出现只是为了研究二分查找的过程,所以没有代码实现,以下借助判定树分析二分查找的时间复杂度。假设满二叉树的结点为n,j为二叉树的层次,则该层共有2^j-1个结点,由于当查找到第j层的结点时,查找也已与给定值key比较了j次。假设每一个结点被查找到的概率相同,那么每一个结点的平均查找次数为:

二分查找与判定树

可见当n较大时,时间复杂度为log(2)n,相比于顺序查找提升了很多。

优缺点分析

优点:查找速度快;

缺点:

1.只适用于顺序存储结构的有序表;

2.修改与删除操作会破坏查找表的有序性,因而二分查找适合于静态查找表;

反思

二分查找的要求是,查找表为采用顺序存储结构的有序表,但现实中的有序性不只是体现在数字的比较上。有很多的排序标准是人为规定的,比如字典序,ABCD.......Z人为规定为升序排列;一个国家中的各个省市,可以根据经纬度的高低排序,或根据GDP产出排序.......总而言之,倘若一个问题适合采用二分查找,前提是适合指定解决该问题的排序规则,从而方便查找的实现。

另外,现实中的查找并不只是限制于一个值,还可以是一个范围,比如老师查找某个成绩段之间的所有学生,公司根据员工的绩效分段给员工发不同的奖金,学校要求科目成绩在[90,100]分段就可以给出A绩点等等......

以上就是我对查找学习的一些反思。文章来源地址https://www.toymoban.com/news/detail-485646.html

到了这里,关于二分查找与判定树的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【算法】二分查找(整数二分和浮点数二分)

    大家好!今天我们来学习二分查找算法,这是一种效率很高的算法哦! 目录 1. 整数二分 2. 整数二分模板 3. 整数二分模板题 3.1 洛谷 P2249 【深基13.例1】查找 3.2 Acwing789. 数的范围 4. 浮点数二分 5. 浮点数二分模板 6. 浮点数二分模板题 6.1 Acwing 790.数的三次方根 6.2 洛谷 P1024 [

    2024年02月10日
    浏览(51)
  • C++二分算法(二分查找&二分答案)细节详解

     二分算法可以分为 二分查找 和 二分答案 。 以在一个 升序数组 中查找一个数为例。它每次考察数组当前部分的 中间元素 ,如果中间元素刚好是要找的,就结束搜索过程;如果中间元素小于所查找的值,那么左侧的只会更小,不会有所查找的元素,只需到右侧查找;如果

    2024年02月08日
    浏览(52)
  • 【Python查找算法】二分查找、线性查找、哈希查找

    目录 1 二分查找算法  2 线性查找算法 3 哈希查找算法         二分查找(Binary Search)是一种用于在有序数据集合中查找特定元素的高效算法。它的工作原理基于将数据集合分成两半,然后逐步缩小搜索范围,直到找到目标元素或确定目标元素不存在。 以下是二分查找的

    2024年02月08日
    浏览(51)
  • 【算法】简单的二分查找算法

    一个简单的二分查找算法:         简单描述:算法由静态方法rank()实现,它接受一个整数键和一个有序的int数组作为参数,如果整数存在于数组,返回它的索引,否则返回-1,算法使用两个变量lo和hi,并保证整数如果存在于数组中则它一定存在于a[lo...hi]中,然后通过循

    2024年01月21日
    浏览(56)
  • 【算法小课堂】二分查找算法

    当我们要从一个序列中查找一个元素的时候,最快想到的方法就是顺序查找法(即:从前到后依次查找)。但这种方法过于无脑,就是暴力的把每个元素都排查一遍。元素个数少的时候还行,一旦元素个数多起来,效率是非常低下,所以在实际中这种查找的方法是被摒弃的。

    2024年02月08日
    浏览(39)
  • Java数据结构与算法:查找算法之二分查找

    大家好,我是免费搭建查券返利机器人赚佣金就用微赚淘客系统3.0的小编,欢迎回到本专栏。在这个冰冷的季节里,我们将一同探讨Java中一种高效的查找算法——二分查找。让我们点燃知识的火花,一同解锁这个查找奇迹的秘密! 二分查找简介 二分查找,也称为折半查找,

    2024年01月21日
    浏览(46)
  • 数据结构算法--1 顺序查找二分查找

    顺序查找时间复杂度为O(n) 我们可以借助Python中的函数enumerate,通过enumerate遍历列表返回其索引和值 也可以通过列表长度依次遍历: 但是二分查找时间复杂度为O(logn):

    2024年02月12日
    浏览(54)
  • 【算法集训】基础算法:二分查找 | 概念篇

    二分枚举,也叫二分查找,指的就是给定一个区间,每次选择区间的中点,并且判断区间中点是否满足某个条件,从而选择左区间继续求解还是右区间继续求解,直到区间长度不能再切分为止。 由于每次都是把区间折半,又叫折半查找,时间复杂度为 O(logn),和线性枚举的求

    2024年04月11日
    浏览(45)
  • 二分查找算法 | 你真的搞懂二分了吗?

    我身边的人都认为二分查找很简单,但事实真是如此吗?不,并不简单。二分算法有着许多的 边界问题 ,当你写着代码一不小心就会陷入死循环。本篇文章会深入细节详细介绍 整数二分算法 以及使用 二分算法步骤 和 力扣题目练习 ,并且还会给出 二分查找算法模板 ,下面

    2023年04月10日
    浏览(45)
  • 算法-二分查找、移除元素

    伪装成一个老手! 给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。 示例 1: 输入: nums = [-1,0,3,5,9,12], target = 9 输出: 4 解释: 9 出现在 nums 中并且下标为 4 来源:力扣二分查找 1. Q1: 为

    2024年02月10日
    浏览(48)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包