精华内容
参与话题
问答
  • 【经典算法】·二分法

    千次阅读 2019-11-25 23:25:29
    二分法 对于区间[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:06:24
        二分法(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);
    	}
    }

    结果测试:



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

    千次阅读 2019-09-18 10:06:14
    二分法 你好! 这是你第一次使用 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;... //二分中点=数组左边界+(右边...
  • 二分法

    2019-05-11 15:20:44
    二分法又称分半法,或对分法,是一种方程式根的近似值求法。二分法经常做为许多算法的优化途径,可以使一些O(n)的算法优化成O(logn)。所以在计算机竞赛中经常使用,为基础算法。 二分法的思想:分而治之。将...
  • Shell算法—二分法

    2018-12-04 17:23:21
    二分法 适用范围为一个已经排好序的数组(升序、降序) (升序数组)步骤: 左端点(l) 右端点(r) 查找的值(key) 中间(m) 数组(arr) 找到数组 l 与 r 让需 key 与 arr[m] 作比较 如果 key &...
  • 算法---二分法

    万次阅读 2016-09-21 22:39:33
    二分法可以归为两大类: * 二分查找算法 * 二分排序算法 * 二分合并算法二分查找算法算法中经常用到二分查找算法,比如最常规的应用就是在一个有序数组中找特定的数,但是如何写出一个完整准确的二分法呢,边界...
  • 二分法查找

    万次阅读 2019-08-04 16:55:11
    二分法查找针对的是一个有序的数据集合,每次通过与区间的中间元素对比,将待查找的区间缩小为之前的一半,直到找到要查找的元素,或者区间被缩小为0 二分查找非常高效,假设数据大小是n,每次查找后数据都会缩小为原来的...
  • C语言二分法查找

    万次阅读 多人点赞 2018-08-19 22:56:52
    所谓的二分查找法,其实是一种有序的查找方法,也称折半查找(Binary Search),如果是无序的则要先进行排序操作。基本思想是:目标值通过与中间元素比较,可分为三种情况: 第一种情况:目标值与中间元素相等,...
  • PHP 实现二分法查找

    万次阅读 2016-08-01 20:10:08
    二分法查找需要数组是一个递增的数组。 想要写出二分法查找的代码,首先要懂得二分法实现查找的原理: ①要知道中间位置就需要知道起始位置和结束位置,然后取出中间位置的值来和我们的值做对比。 ②如果中间值大于...
  • 二分法查找详解

    万次阅读 2018-05-24 20:26:53
    二分法查找从概念上很好理解,困难的地方在于有几个细节需要注意: 1.循环执行条件。 2.递进方式。 3返回值的问题,返回左右边界值还是返回一个存储结果的中间变量。 以一个最常见的游戏为例,甲从0~9中随便选择一...
  • 二分法查找MATLAB程序

    2018-03-27 23:18:53
    使用二分法查找的MATLAB程序编写,方便刚接触MATLAB的同学分享学习。
  • 二分法查找是经典算法,这篇博客用循环和递归两种反方式实现了二分法查找。这篇博客有完整的代码实现以及查找过程的文字详述。
  • 二分法查找例子

    千次阅读 2011-05-03 10:37:00
    #define SEARCH_NOT_FOUND -1 //.../* 二分法查找[递归实现版本] */ /* arr: 待查找的数组 */ /* first: 搜索开始下标 */ /* last: 搜索结束下标的后一位置 */ /*

空空如也

1 2 3 4 5 ... 20
收藏数 63,817
精华内容 25,526
关键字:

二分法