二分法_二分法查找 - CSDN
精华内容
参与话题
  • 【经典算法】·二分法

    千次阅读 2019-11-29 09:04:09
    二分法 对于区间[a,b][a,b][a,b]上连续不断且f(a)⋅f(b)<0f(a)·f(b)<0f(a)⋅f(b)<0的函数y=f(x)y=f(x)y=f(x),通过不断地把函数f(x)f(x)f(x)的零点所在的区间一分为二,使区间的两个端点逐步逼近零点...

    联系作者:humminwang@163.com

    二分法

    • 对于区间[ab][a,b]上连续不断且f(a)f(b)<0f(a)·f(b)<0的函数y=f(x)y=f(x),通过不断地把函数f(x)f(x)的零点所在的区间一分为二,使区间的两个端点逐步逼近零点,进而得到零点近似值的方法叫二分法。
    • 通俗语言就是将搜索空间不断的减半,从而逼近解的过程。

    从二分查找来看二分法:

    例子:在一个一维 有序 数组中,判断数组中是否有值为targettarget的数存在。

    • 首先判断数组中间值是否大于目标值,如果大于,则将搜索空间变为前半段,删除后半段。反之同理。

    迭代算法(时间复杂度O(log(n)),空间复杂度O(1))

    int binarySearch(vector<int> arr,int key){
    	int low=0; //数组最小索引值
    	int high=arr.size()-1; //数组最大索引值
    	while(low<high){
    		int mid==(low+high)/2;
    		if(key==arr[mid]){
    			return mid+1;
    		}else if(key>arr[mid]){
    			low=mid+1;
    		}else{
    			high=mid-1;
    		}
    	}
    	return -1;//没有找到
    }
    

    递归算法(时间复杂度O(log(n)),空间复杂度O(n))

    int binarySearch(vector<int> arr,int low,int high,int key){
    	if(low>high){return -1;}
    	int mid=(low+high)/2;
    	if(key==arr[mid]){
    		return mid+1;
    	}else if(key<arr[mid]){
    		high=mid-1;
    		return binarySearch(arr,low,high,key);
    	}else{
    		low=mid+1;
    		return binarySearch(arr,low,high,key);
    	}
    }
    
    Reference:
    展开全文
  • 常用算法解析------二分法

    千次阅读 2019-05-18 16:41:55
        二分法(Bisection method) 即一分为二的方法. 设[a,b]为R的闭区间. 逐次二分法就是造出如下的区间序列([an,bn]):a0=a,b0=b,且对任一自然数n,[an+1,bn+1]或者等于[an,cn],或者等于[cn,bn],其中...

    该文章的很多思想来自《算法图解》(著:Aditya Bhargava,译:袁国忠)

    定义

        二分法(Bisection method) 即一分为二的方法. 设[a,b]为R的闭区间. 逐次二分法就是造出如下的区间序列([an,bn]):a0=a,b0=b,且对任一自然数n,[an+1,bn+1]或者等于[an,cn],或者等于[cn,bn],其中cn表示[an,bn]的中点.

    算法思想

        当数据量很大适宜采用该方法。采用二分法查找时,数据需是排好序的,假设数据是按升序排序的。
        基本思想如下:
    对于给定值key,从序列的中间位置midmid开始比较,lowlow为初始位置,highhigh为末尾位置,
    如果当前位置arr[mid]arr[mid]值等于keykey,则查找成功;
    keykey小于当前位置值arr[mid]arr[mid],则在数列的前半段中查找,arr[low,mid1]arr[low,mid-1]
    keykey大于当前位置值arr[mid]arr[mid],则在数列的后半段中继续查找arr[mid+1,high]arr[mid+1,high]
    直到找到为止。
        二分法的时间复杂度为:O(log2(n))O(\log_2(n))nn为序列长度。

    举例如下

        对于[1, 100]这100个数字组成的序列中,找到数字15所在的位置,那么利用二分法图例如下:

        这样我们利用了5步就找到目标值15的位置。二分法的时间复杂度为:O(log2(n))O(\log_2(n)),普通枚举法的时间复杂度为:O(n)O(n),其中nn为序列长度。由此可以看出,数据量越大,二分法的优势就越明显。

    编码实现

    #  注意这里的pre_list必须是有序的
    def binary_search(pre_list, target):
        low = 0
        mid = None
        high = len(pre_list) - 1
        # 如果目标值越界,则直接返回 None
        if target < pre_list[low] or target > pre_list[high]:
            return mid
        # 如果目标值在范围内,再进行处理
        while low <= high:
            mid = int(low / 2 + high / 2)
            if target == pre_list[mid]:
                break
            elif target < pre_list[mid]:
                high = mid - 1
            else:
                low = mid + 1
        return mid
    展开全文
  • 算法——二分法查找(binarySearch)

    万次阅读 多人点赞 2018-04-11 14:52:35
    二分法查找,也称为折半法,是一种在有序数组中查找特定元素的搜索算法。二分法查找的思路如下:(1)首先,从数组的中间元素开始搜索,如果该元素正好是目标元素,则搜索过程结束,否则执行下一步。(2)如果目标...

    二分法查找,也称为折半法,是一种在有序数组中查找特定元素的搜索算法。

    二分法查找的思路如下:

    (1)首先,从数组的中间元素开始搜索,如果该元素正好是目标元素,则搜索过程结束,否则执行下一步。

    (2)如果目标元素大于/小于中间元素,则在数组大于/小于中间元素的那一半区域查找,然后重复步骤(1)的操作。

    (3)如果某一步数组为空,则表示找不到目标元素。

    二分法查找的时间复杂度O(logn)。

    非递归算法:

    function binarySearch(arr,key){
    	var low=0; //数组最小索引值
    	var high=arr.length-1; //数组最大索引值
    	while(low<=high){
    		var mid=Math.floor((low+high)/2);
    		if(key==arr[mid]){
    			return mid;
    		}else if(key>arr[mid]){
    			low=mid+1;
    		}else{
    			high=mid-1;
    		}
    	}
    	return -1; //low>high的情况,这种情况下key的值大于arr中最大的元素值或者key的值小于arr中最小的元素值
    }

    结果测试:


    递归算法:

    function binarySearch(arr,low,high,key){
    	if(low>high){return -1;}
    	var mid=Math.floor((low+high)/2);
    	if(key==arr[mid]){
    		return mid;
    	}else if(key<arr[mid]){
    		high=mid-1;
    		return binarySearch(arr,low,high,key);
    	}else{
    		low=mid+1;
    		return binarySearch(arr,low,high,key);
    	}
    }

    结果测试:



    展开全文
  • 二分法原理及代码实现

    千次阅读 2020-04-08 18:31:39
    二分法 你好! 这是你第一次使用 Markdown编辑器 所展示的欢迎页。如果你想学习如何使用Markdown编辑器, 可以仔细阅读这篇文章,了解一下Markdown的基本语法知识。 算法步骤 步骤1: 准备 计算f(x)在有根区间[a,b]...

    二分法

    一个函数在定义域内单调有根,通过将根区间不断等分寻找近似解或精确解的方法。

    算法步骤

    步骤1: 准备 计算f(x)在有根区间[a,b]端点处的值f(a),f(b).
    步骤2: 二分 计算f(x)在区间中点 (a+b)/2处的值 f((a+b)/2).
    步骤3: 判断 若f((a+b)/2)=0,则(a+b)/2即是根,计算过程结束,否则检验;若f((a+b)/2)f(a)<0,则以(a+b)/2代替b,否则以(a+b)/2代替a.

    反复执行步骤2和步骤3,直到区间[a,b]的长度小于允许误差e,此时中点(a+b)/2即为所
    求近似根。

    算法流程

    例题

    例:证明方程x3 +x-4=0在[1,3]内有一个根;若采用对分区间法求误差的绝对值不大于10-3的近似根,则至少迭代计算多少次?

    源码

    // An highlighted block
    #include "stdio.h"
    #include "math.h"
    #define f(x) (x*x*x+x-4)   /*定义原函数,此函数需要是单调的*/
    #define e 0.001      /*迭代误差*/
    main()
    {
     int i=0;
     float x,a=1,b=3,y=f(a);   /*定义根区间初始值*/
     if(y*f(b)>=0)    /*检验根的存在性*/
     {
      printf("\nThe range is error!");
      return 0;
     }
     else   /*若根存在,开始二分迭代*/
      do
       { x=(a+b)/2;
         printf("\nx%d=%6.4f",i,x);
         i++;
         if (f(x)==0) break;  /*函数值为零停止,得到精确解*/
         if(y*f(x)<0)
           b=x;
         else
           a=x;
        }while(fabs(b-a)>e);    /*误差小于e时停止迭代,得到近似解*/
     printf("\nx=%4.2f",x);
    }
    

    计算结果

    在这里插入图片描述

    展开全文
  • 二分法的两种写法

    万次阅读 2018-07-24 09:00:29
    1.循环写法 public static int rank(int key,int nums[]) {  //查找范围的上下界  int low=0;  int high=nums.length-1;  //未查找到的返回值  int notFind=-1;... //二分中点=数组左边界+(右边...
  • 二分法

    千次阅读 2018-10-30 16:14:38
    二分法的简单理解 二分法在数学上的概念是,对于在区间{a,b}上连续不断,且满足f(a)f(b)&amp;lt;0的函数y=f(x),通过不断地把函数f(x)的零点所在的区间二等分,使区间的两个端点逐步逼近零点,进而得到零点...
  • 二分法查找时间复杂度计算

    万次阅读 2016-10-07 16:40:00
    查找数据长度为N,每次查找后减半, 第一次 N/2 ... 第k次 N/2^k 最坏的情况下第k次才找到,此时只剩一个数据,长度为1。 即 N/2^k = 1 查找次数 k=log(N)。
  • 利用matlab编写二分法求根函数

    万次阅读 多人点赞 2016-10-15 10:14:14
    刚好接触到了matlab的编程方面的内容,就想着自己编制一个简单的二分法求根的程序。 我的思路是:用户任意输入求根区间和求根精度,函数自动根据求根区间和求根精度,进行递归调用,最后输入满足精度要求的根。 废话...
  • matlab 二分法

    千次阅读 2017-09-08 19:14:53
    matlab 二分法
  • 【源码】二分法及MATLAB实现

    万次阅读 2018-10-08 09:22:10
    二分法是一种求解给定函数根的数值方法。二分法的实质是通过不断地把函数f(x)零点所在的区间一分为二,使区间的两个端点逐步逼近零点,进而得到零点近似值。 将m = (a+b)/2作为新的b端点,继续重复以上步骤,直到...
  • 排序算法之 二分法排序

    万次阅读 2018-08-08 22:44:59
    之所以单独来二分法排序,是因为近些天一直在做二分法查找的问题,延伸只二分法排序,做此记录,以便于以后记忆。 首先了解下二分法的思想:对于区间[a,b]上连续不断且f(a)·f(b)&lt;0的函数y=f(x),...
  • 二分法查找的C++实现

    万次阅读 2016-03-11 15:05:44
    二分法查找,简单来说就是每次去一个有序数列的中间数,然后和目标值比对,如果不是的话,大的就在中间值的右边查找,小的话就在中间值的左边查找。是最初级的算法,用C++实现。 #include using namespace std; ...
  • 查找与排序之二分法查找篇(C语言实现)

    万次阅读 多人点赞 2016-03-21 20:59:07
    相比线性查找,二分法查找则显得十分高效,其查找次数与总元素数量存在对数关系,即只要较少的查找次数就可以完成快速地搜索。下面实现二分法查找: 原理:在进行二分法查找前需要先对数据进行排序(具体排序实现...
  • 题目:用二分法求方程x3-x-1=0在[1,2]内的近拟解,要求误差不超过0.001。 要求,用matlab写出编码, x_up = 2; x_down = 1; error = 0.001; res_down = x_down^3 - x_down - 1; res_up = x_up^3 - x_up - 1; ...
  • 二分法c语言代码(递归、迭代)

    万次阅读 多人点赞 2017-06-11 08:19:25
    二分法c语言代码(递归、迭代)
  • 二分法查找(java实现)

    万次阅读 2018-10-09 09:04:01
    二分法适用于已经排好序的数组,定义两个变量,一个low,一个high,则mid=(low+high)/2 算法核心: 如果 value==arr[mid],中间值正好等于要查找的值,则返回下标,return mid; 如果 value&lt;arr[mid],要找的值...
  • Java 二分法查找

    万次阅读 2018-05-21 21:45:46
    采用二分法查找时,数据需是有序不重复的。 基本思想:假设数据是按升序排序的,对于给定值 x,从序列的中间位置开始比较,如果当前位置值等于 x,则查找成功;若 x 小于当前位置值,则在数列的前半段中查找;若 x ...
  • python 二分法查找

    千次阅读 2018-10-19 20:48:40
    # 给定一个排好序(升序)的列表与待查找的关键字,成功则返回其索引,失败则返回-1。 def search(list, key): left = 0 # 左边界 right = len(list) - 1 # 右边界 while left &lt;= right: ...
  • 二分法的使用之MATLAB实现

    万次阅读 2010-11-08 12:17:00
    今天数值计算上机做了一个验证二分法计算非线性方程的实验。以前没有想过这个问题,今天作业一下感觉这个方法确实不错,随记下来。首先给出要计算的方程:f(x)=x^2=M然后编写算法:MATLAB code:%其中a,b表示查找根...
  • 二分法求平方根

    千次阅读 2018-11-22 16:27:15
    利用二分法求一个数的平方根,精度要求 e &lt; 10^-6; 2.思路 1.要求x(x&gt;0)的完全平方根,则二分法范围为[low,up] 其中 low = 0, up = x 2.令mid = (up+low)/2 3.以fabs(mid * mid - x) &gt;=...
1 2 3 4 5 ... 20
收藏数 59,830
精华内容 23,932
关键字:

二分法