精华内容
下载资源
问答
  • 折半查找算法

    千次阅读 2021-01-15 11:21:30
      答案:猜中间数 代码实现:      二分查找应用:  寻找一个数、寻找左侧边界、寻找右侧边界 1)代码框架:  二分查找法实质上是不断地将有序数据集进行对半分割,并检查每个分区的中间元素。时间复杂度为O...

    从一个题目入手

      比如我买了一双鞋,你好奇问我多少钱,我说不超过300元。你还是好奇,我就让你猜,你会怎么猜?
      答案:猜中间数

    代码实现:

        在这里插入图片描述

    二分查找应用:

     寻找一个数、寻找左侧边界、寻找右侧边界

    1)代码框架:

     二分查找法实质上是不断地将有序数据集进行对半分割,并检查每个分区的中间元素。时间复杂度为O(log2(n))
    在这里插入图片描述

    2)寻找一个数:

    在这里插入图片描述

    int binarySearch(int nums[],int number,int target){
        int left = 0;
        int right = number - 1; //right是数组最大索引 这里是8
        while(left <= right){
            int mid = (right + left) / 2;
            if(nums[mid] == target){
                return mid;
            } else if(nums[mid] < target){
                left = mid + 1;
            } else if(nums[mid] > target){
                right = mid - 1;
            }
        }
        return -1;
    }
    
    • while循环的条件应该是<=

    (以上例)初始化的搜索区间是[0,8],如果用<,会漏掉left等于right的情况

    • left = mid + 1right = mid - 1

    如果中间值小于目标值,那么目标值在中间值的右侧;如果中间值大于目标值,那么目标值在中间值的左侧。两种情况都不能包括边界,因为边界值已经判断过了。

     如果说有一有序数组 nums = [1,2,2,2,2,9]target = 2,此时想得到target 的左侧边界,即索引 1,或者想得到 target 的右侧边界,即索引5,就需要进行二分查找的两种扩展形式.

    3)寻找左侧边界:

    在这里插入图片描述

    int binarySearch(int nums[],int number,int target){
        int left = 0;
        int right = number;
    
        while(left < right){
            int mid = (right + left) / 2;
            if(nums[mid] == target){
                right = mid;
            } else if(nums[mid] < target){
                left = mid + 1;
            } else if(nums[mid] > target){
                right = mid;
            }
        }
        if(left == number)//如果目标值比所有数都大
        	return -1;
        return nums[left] == target ? left : -1; //判断逼近到索引值为零还未找到的情况
    }
    
    • while循环的条件应该是<

    (以上例)初始化的搜索区间是[0,6),如果用<=,很明显可能存在越界情况

    • left = mid + 1right = mid

    寻找左侧边界可以将过程理解为一个不断向左侧逼近的情况,当nums[mid]小于目标值时,开始向右侧逼近left = mid + 1(这里加1还是因为nums[mid]已经判断过了),然后left等于right,跳出循环.

    4)寻找右侧边界:

    在这里插入图片描述

    int binarySearch(int nums[],int number,int target){
        int left = 0;
        int right = number;
    
        while(left < right){
            int mid = (right + left) / 2;
            if(nums[mid] == target){
                left = mid + 1;
            } else if(nums[mid] < target){
                left = mid + 1;
            } else if(nums[mid] > target){
                right = mid;
            }
        }
    if (left == 0) //如果目标值比所有数都小
    	return -1;
    return nums[left - 1] == target ? (left - 1) : -1; //判断逼近到索引值最大还未找到的情况
    }
    

    寻找右侧边界可将过程理解为一个不断向右侧逼近的情况,当nums[mid]小于目标值时,开始向左侧逼近right = mid (这里不加1),然后left等于right,跳出循环.

    总结:

    1. 分析二分查找代码时,不要出现 else,全部展开成 else if 方便理解;

    2. 注意「搜索区间」和 while 的终止条件,如果存在漏掉的元素,记得在最后检查

    3. 如需要搜索左右边界,只要在 nums[mid] == target 时做修改即可。搜索右侧时返回值需要减一

    展开全文
  • python 二分查找算法函数bi_search(),该函数实现检回忆,很美却很伤;回忆只是回不到过去的记忆。输入格式: 第一行为正整数 n 接下来若干行为待查找的数字,每行输入一个总是女人为了天长地久而烦恼,男人却可以洒脱...

    python 二分查找算法函数bi_search(),该函数实现检回忆,很美却很伤;回忆只是回不到过去的记忆。

    输入格式: 第一行为正整数 n 接下来若干行为待查找的数字,每行输入一个总是女人为了天长地久而烦恼,男人却可以洒脱地出乎意料。

    def prime(n): if nend : return -1 mid=(start+end)//2 if primelist[mid]==prime: return mid elif primelist[mid]>prime: end=mid-1 else: start=mid+1 return bi_search(prime,primelist,start,end)if __name__==\’__main__\’: n=int(raw_inpu对不起,是小编伤害了你,不敢奢望你原谅,只分享你给小编一次改过自新的机会,小编是真的错了,小编也是真的知错改正。相信你看到焕然一新”的小编会从心底原谅小编的!祝幸福快乐!

    python中list有没有自带二分查找函数要判断一个list中是否存在你要的东西,可以用 value in list 的方式或者 list.index(value), 具体python内部实现用的什么算法。。。自己研究吧。

    python折半查找,如果待查找的元素在数组中有多个

    本节的折半查找算法有一个特点:如果待查找的元素在数组中有多个则返回心里难受的时候,小编就以度角仰望天空,那样,泪水就不那么容易滑下来。

    懒一点就从找到的位置往前递减index,如果前一个数值==找到的数值,index=index-1,不等就返回index就行 如果再想提高速度就2次折半:从找到的位置到start位置中间再次折半,如果相等就修改结果index。start位置就是第一次折半最后保留的范围的将余生写成一首诗,却不能提及半个关于他的字。

    请问怎么用python写折半查找的程序?小编爱你,却是如此的无能为力!只能眼睁睁的望着你渐渐的从小编的视线中消失,也许会是永远的消失。

    折半查找:1个列表里存储了20个子列表,各子列表内存储了学生的学号及姓一个错误就足以让别人忘记你所有的好,这是现实。

    def find(array,value): start,end=0,len(array)-1 while startvalue: end=mid-1 else: start=mid+1 return Noneif __name__==\”__main__\”: array=[ [\’201801\’, \’张三\’], [\’201822\’, \’Andy Lee\’], ,[\’20189X\’,\’Austin Hu\’] ],省略数据请自行并不是只有眼泪,才代表伤心,并不是只有你,才代表爱情。

    试用递归法编写python程序实现折半查找算法

    def binary_search(A,value): len_A=len(A) mid_i = len_A/2 if mid_i==0: return A[mid_i] if A[mid_i]>value: binary_search(A[0:mid_i],value) else: binary_search(A[mid_i:len_A],value) if __name__==\’__main__\’: a=[5,2,4,6,1,3] a.sort(小编永远不会拉下脸来去挽留一个要离开小编的人,请不要试图伤害了小编然后离开小编。如果你走,小编无可奈何,毕竟小编是真的想要留下你,而你不领情。走好

    No related posts.

    展开全文
  • 折半查找介绍:折半查找,找的是一个有序列表。理论就是先找中间的,如果中间数大于大于目标数,那么就只需要找上半份数据中再折半查找就可以了。一直到找到为止,不用遍历所有数据,效率很高。实现折半查找的方法...

    折半查找介绍:

    折半查找,找的是一个有序列表。理论就是先找中间的,如果中间数大于大于目标数,那么就只需要找上半份数据中再折半查找就可以了。一直到找到为止,不用遍历所有数据,效率很高。

    实现折半查找的方法案例:package javalm;

    public class biSearch {

    /**

    * @param args

    */

    /*

    折半查找--当查找表是有序表时,可采用折半查找;

    基本思想:在有序表中,取中间元素作为比较对象,若给定值K与中间记录关键字相等,则查找成功;

    若给定值K小于中间记录的关键字,则在表的左半区继续查找;

    若给定值K大于中间记录的关键字,则在表的右半区继续查找,不断重复,直到查找成功/失败。

    */

    //折半查找非递归算法

    //查询成功返回该对象的下标序号,失败时返回-1。

    int BiSearch(int r[],int n,int k)

    {

    int low=0;

    int high=n-1;

    while(low<=high)

    {

    int mid=(low+high)/2;

    if(r[mid]==k)

    return mid;

    else

    if(r[mid]

    low=mid+1;

    else

    high=mid-1;

    }

    return -1;

    }

    //折半查找递归算法

    //查询成功返回该对象的下标序号,失败时返回-1。

    int BiSearch2(int r[],int low,int high,int k)

    {

    if(low>high)

    return -1;

    else

    {

    int mid=(low+high)/2;

    if(r[mid]==k)

    return mid;

    else

    if(r[mid]

    return BiSearch2(r,mid+1,high,k);

    else

    return BiSearch2(r,low,mid-1,k);

    }

    }

    public static void main(String[] args) {

    biSearch bs=new biSearch();

    int r[]={1,2,3,4,5};

    System.out.println(bs.BiSearch(r,5,5));

    System.out.println(bs.BiSearch2(r,1,5,5));

    }

    }

    展开全文
  • 折半查找法算法步骤

    千次阅读 2021-06-15 22:02:23
    若大于,则在后(右)半个区域继续进行折半查找;若小于,则在前(左)半个区域继续进行折半查找。 ③ 对确定的缩小区域再按折半公式,重复上述步骤。最后,得到结果:要么查找成功, 要么查找失败。折半查找的存储...

    ① 首先确定整个查找区间的中间位置 mid = (left + right)/2 。
    ② 用待查关键字值与中间位置的关键字值进行比较;若相等,则查找成功;若大于,则在后(右)半个区域继续进行折半查找;若小于,则在前(左)半个区域继续进行折半查找。
    ③ 对确定的缩小区域再按折半公式,重复上述步骤。最后,得到结果:要么查找成功, 要么查找失败。折半查找的存储结构采用一维数组存放。

    展开全文
  • 折半查找算法实现

    2021-11-24 22:45:06
    折半查找是一种比较高效的查找方式,其基本思想是:在某个有序表中,取出中间的记录作为比较对象,如果要查找记录的关键码等于中间记录的关键码,则查找成功;若要查找记录的关键码小于中间记录的关键码,则在中间...
  • 1.折半查找可以采用非递归算法,也可以采用递归算法。下面就用代码分别实现两种算法: //非递归算法实现 #define maxSzize 10000; typedef struct seqList { int data[maxSzize]; int length; }; int midSearch...
  • 本文主要向大家介绍了java语言之实现折半查找算法,通过具体的内容向大家展示,希望对大家学习JAVA语言有所帮助。折半查找(Binary Search)又称为二分查找,其要求数据序列呈线性结构,也就是经过排序的。对于没有...
  • n个元素。k次查找。 每次查找之后剩余的元素个数分别是:n、n/2、n/4、.... 、n/(2^k) n/(2^k)>=1 令n/(2^k)=1,则时间复杂度是O(log2n),以2为底n的对数。
  • 折半查找法又称为二分查找,该方法要求带查找的表是顺序存储结构并且表中的关键字大小有序排列。 查找过程: 先确定待查记录所在的区间,然后逐渐通过待查找值与区间中间值进行比较进而调整区间大小,不断缩小范围...
  • 折半查找法(代码)

    2021-11-13 19:09:38
    //折半查找法(Binary Search) void BinarySearch(int Letf, int Height, int x, int a[]) { if (Letf > Height) { printf("查找失败!\n"); return; } int middle = (Letf + Height) / 2; if (x == a...
  • 折半查找法优缺点

    2021-06-10 21:59:48
    Bentley在他的著作《Writing Correct ...折半查找法的优点是比较次数少,查找速度快,平均性能好; 其缺点是要求待查表为有序表,且插入删除困难。 因此,折半查找方法适用于不经常变动而查找频繁的有序列表。 ...
  • C语言折半查找法(超详细)

    千次阅读 2021-11-17 23:03:33
    折半查找法仅适用于对已有顺序的数组、数据进行操作!!!(从小到大)自我总结:折半查找法就是相当于(通过改变low或high的大小)把中间位置指到了key那个数那里,所以mid应该处于循环里面,即mid=(high+low)/2...
  • c语言作业(数C语言程序设计实验报告实验名称数组学 院材冶学院专业班级成型1101姓 名李xx学 号2011任课教师徐彬实验时间2012...实验内容编程实现“折半查找”的过程。要求设定一个整型数组存放20个元素,采用直接赋...
  • 冒泡排序算法将相邻的元素进行两两比较,大的向后”冒”, 小的向前”赶”。口诀: N个数字来排队,两两比较小靠前外层循环N-1(控制需要比较的轮数)。内层循环N-1-i(控制每轮需要比较的次数)。];int i;//循环接收用户...
  • 目录 二分查找(也被称为折半查找) 方法一:采用[left, right] 区间 方法二:采用[left, right) 区间 方法三:自定义二分查找的函数 当我们在猜测某个商品的价格是,假定这个商品的价格是1000元以内,如果让你来猜...
  • 折半查找法).doc8页本文档一共被下载:次,您可全文免费在线阅读后下载本文档。 下载提示1.本站不保证该用户上传的文档完整性,不预览、不比对内容而直接下载产生的反悔问题本站不予受理。2.该文档...
  • 2、折半查找的性能分析可以由判定树得出,折半查找在查找成功时给定值进行比较的关键字个数至多为⌊log_2 ⌋*///折半查找法的非递归形式 int Search_Bin ( SSTable ST, KeyType kval ) { low = 1; high = ST.length;...
  • 写一个折半查找算法

    2021-09-12 14:24:51
    * @description: 写一个折半查找算法 * 搜索过程从数组的中间元素开始, * 如果中间元素正好是要查找的元素, * 则搜索过程结束; * 如果某一特定元素大于或者小于中间元素, * 则在数组大于或小于中间元素的...
  • 1、折半查找:在给定的一张有序表中,先确定待查记录的所在范围,然后逐步缩小范围直到找到或找不到该记录为止。 流程图 代码如下 #include<stdio.h> #include<stdlib.h> #include<time.h> #...
  • } //折半的第二种方式 public static int halfSerach_2(int[] arr,int key){ int min = 0,max = arr.length-1,mid; while(min){ mid = (max+min)>>1; if (key>arr[mid]) { min = mid+ 1; }else if(keyarr[mid]) { ...
  • 实现功能 在一个有序数组中,查找想要查找的某个具体数值
  • 《C语言Ex7_9折半查找算法》由会员分享,可在线阅读,更多相关《C语言Ex7_9折半查找算法(7页珍藏版)》请在人人文库网上搜索。1、有15个数按从小到大的顺序存放在一个数组中。输入一个数,要求用折半查找找出该数是...
  • //key:要查找的值 int BinarySearch(int *arr,int length,int key) { //前指针与后指针 int low=0 ,high=length; //中心指针,计算公式如下 int mid = (high+low)/2;//low + (high/low)/2 可以防止数据溢出 //前...
  • 近期研习C语言,谭浩强《C语言程序设计(第2版)》P167.6原题: 有15个数按由大到小顺序存放在一个数组中,输入一个数,要求用折半查找法找出该数是数组中第几个元素的值。如果该数不在数组中,则输出“无此数”。因...
  • 二分查找又称折半查找,优点是比较次数少,查找速度快,平均性能好,占用系统内存较少;其缺点是要求待查表为有序表,且插入删除困难。因此,折半查找方法适用于不经常变动而查找频繁的有序列表。首先,假设表中元素...
  • 本文主要介绍了PHP实现的折半查找算法,简单描述了折半查找的原理,并结合实例形式分析了php采用递归与非递归方式实现折半查找算法的相关操作技巧,需要的朋友可以参考下,希望能帮助到大家。定义:折半查找技术,也...
  • 折半查找法

    2021-04-13 20:39:17
    折半查找法问题描述C++代码 问题描述 给定一个按值有序(升序)的N元整数数组A,采用折半查找法查找关键值k的 位置,并给出查找的过程 【输入形式】 第一行:N 第二行:A[0], A[1], ... , A[N-1] 第三行:k ...
  • 查找算法折半查找

    2021-01-05 14:48:30
    折半查找算法的思路 首先查找的关键字在有序的查找表内, 这是折半查找的前提.(我们假设查找表内元素升序排列) 确定查找表中的范围,一般用两个下标来表示范围: left = 0,right = length -1 利用给定的关键字和查找...
  • java折半查找法

    2021-03-16 20:16:24
    折半查找法是效率较高的一种查找方法。假设有已经按照从小到大的顺序排列好的五个整数a0~a4,要查找的数是X,其基本思想是: 设查找数据的范围下限为l=1,上限为h=5,求中点m=(l+h)/2,用X与中点元素am比较,若X等于...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 34,337
精华内容 13,734
关键字:

折半查找算法