精华内容
下载资源
问答
  • 二分搜索算法详解(Binary Search)

    千次阅读 多人点赞 2020-12-26 20:35:54
    二分搜索(Binary Search) 如何确定一个元素在数组中的位置?(假设数组里面全都是整数) 如果是无序数组,从第0个位置开始遍历搜索,平均时间复杂度:O(n) 如果是有序数组,可以使用二分搜索,最坏时间复杂度为O...

    二分搜索(Binary Search)

    • 如何确定一个元素在数组中的位置?(假设数组里面全都是整数)

    • 如果是无序数组,从第0个位置开始遍历搜索,平均时间复杂度:O(n)
      在这里插入图片描述

    • 如果是有序数组,可以使用二分搜索,最坏时间复杂度为O(logn)
      在这里插入图片描述

    (一)、二分搜索 — 思路

    • 假设在[beginend)范围内搜索某个元素 vmid == (begin + end)/ 2
      ①、如果v < m,去[beginmid)范围内二分搜索
      ②、如果v > m,去[mid + 1, end)范围内二分搜索
      ③、如果v == m ,直接返回 mid
    • end指的是数组的长度。
      在这里插入图片描述

    (二)、二分搜索 — 实例

    在这里插入图片描述
    在这里插入图片描述

    (三)、二分搜索 — 实现

    import org.junit.Test;
    import java.util.Arrays;
    
    /**
    * 查找v在有序数组array中的位置
    */
    public class BinarySearch {
        public int indexOf(int[] array, int v){
            if (array == null || array.length == 0) return -1;
            int begin = 0;
            int end = array.length;
            while (begin < end){
                int mid = (begin + end) >> 1;
                if (v < array[mid]){
                    end = mid;
                }else if (v > array[mid]){
                    begin = mid+1;
                }else {
                    return mid;
                }
            }
            return -1;
        }
        @Test
        public void test(){
            int[] array = {2,4,8,8,9,13,10};
            System.out.println(Arrays.toString(array));
            System.out.println(indexOf(array,8));
        }
    }
    运行结果:
    [2, 4, 6, 8, 9, 13, 10]
    3
    
    • 思考???
      如果存在多个重复的值,返回的是哪一个?
    • 例如:[2,4, 8, 8, 9, 13, 10]
      我们通过运行上述的代码,可以看到,它的返回值是3,而不是2,因此我们可以得出结论如果存在多个重复的值,返回的值不确定。

    (四)、二分搜索优化

    • 在元素 v 的插入过程中,可以先用二分搜索出合适的插入位置,然后再将元素v插入。
      在这里插入图片描述
    • 要求二分搜索返回的插入位置:第1个大于 v 的元素位置
      ①、如果 v 是 5,返回 2
      ②、如果 v 是 1,返回 0
      ③、如果 v 是 15,返回 7
      ④、如果 v 是 8,返回 5

    (1)、二分搜索优化 — 思路

    • 假设在[beginend)范围内搜索某个元素 vmid == (begin + end)/ 2
      ①、如果v < m,去[beginmid)范围内二分搜索
      ②、如果v >= m,去[mid + 1, end)范围内二分搜索
    • end指的是数组的长度。
      在这里插入图片描述

    (2)、 二分搜索优化 — 实例

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    import org.junit.Test;
    import java.util.Arrays;
    
    public class BinarySearch {
        /**
         * 查找v在有序数组array中待插入位置
         */
        public static int search(int[] array, int v){
            if (array == null || array.length == 0) return -1;
    
            int begin = 0;
            int end = array.length;
            while (begin < end){
                int mid = (begin + end) >> 1;
                if (v < array[mid]){
                    end = mid;
                }else{
                    begin = mid+1;
                }
            }
            return begin;
        }
    
        @Test
        public void test2(){
            int[] array = {2,4,8,8,8,12,14};
            System.out.println(Arrays.toString(array));
            System.out.println(search(array,5) == 2);
            System.out.println(search(array,1) == 0);
            System.out.println(search(array,15) == 7);
            System.out.println(search(array,8) == 5);
        }
    }
    运行结果:
    [2, 4, 8, 8, 8, 12, 14]
    true
    true
    true
    true
    
    展开全文
  • 二分搜索算法解题步骤,吐血整理

    千次阅读 2020-11-25 23:11:25
    二分搜索(折半搜索)是一种在有序数组中查找某一特定元素的搜索算法。从定义可知,运用二分搜索的前提是数组必须是排好序的。另外,输入并不一定是数组,也有可能是给定一个区间的起始和终止的位置。 他的时间...

    基本介绍

    二分搜索(折半搜索)是一种在有序数组中查找某一特定元素的搜索算法。从定义可知,运用二分搜索的前提是数组必须是排好序的。另外,输入并不一定是数组,也有可能是给定一个区间的起始和终止的位置。

    他的时间复杂度是 O(lgn),非常高效。

    特点

    他的缺点要求待查找的数组或者区间是排好序的。

    对数组进行动态的删除和插入操作并完成查找,平均复杂度会变为 O(n)。

    因此,当输入的数组或者区间是排好序的,同时又不会经常变动,而要求从里面找出一个满足条件的元素的时候,二分搜索就是最好的选择。

    解题思路

    二分搜索一般化的解题思路如下。

    • 从已经排好序的数组或区间中取出中间位置的元素,判断该元素是否满足要搜索的条件,如果满足,停止搜索,程序结束。

    • 如果正中间的元素不满足条件,则从它两边的区域进行搜索。由于数组是排好序的,可以利用排除法,确定接下来应该从这两个区间中的哪一个去搜索。

    • 通过判断,如果发现真正要找的元素在左半区间的话,就继续在左半区间里进行二分搜索。反之,就在右半区间里进行二分搜索。

    二分查找的解题框架

    int binarySearch(int[] nums, int target) {
        int left = 0, right = ...;
    
        while(...) {
        	//计算 mid 时需要技巧防止溢出,建议写成: mid = left + (right - left) / 2
            int mid = (right + left) / 2;
            if (nums[mid] == target) {
                ...
            } else if (nums[mid] < target) {
                left = ...
            } else if (nums[mid] > target) {
                right = ...
            }
        }
        return ...;
    }
    

    常见解法

    递归解法

    例题:假设我们要从一个排好序的数组里 {1, 3, 4, 6, 7, 8, 10, 13, 14} 查看一下数字 7 是否在里面,如果在,返回它的下标,否则返回 -1。

    递归写法的代码模板如下。

    // 二分搜索函数的定义里,除了要指定数组 nums 和目标查找数 target 之外,还要指定查找区间的起点和终点位置,分别用 low 和 high 去表示。
    int binarySearch(int[] nums, int target, int low, int high) {
            // 为了避免无限循环,先判断,如果起点位置大于终点位置,表明这是一个非法的区间,已经尝试了所有的搜索区间还是没能找到结果,返回 -1。 
    
    	if (low > high) {
            return -1;
        }
        // 取正中间那个数的下标 middle。
        int middle = low + (high - low) / 2;
        
        // 判断一下正中间的那个数是不是要找的目标数 target,是,就返回下标 middle。    
        if (nums[middle] == target) {
            return middle;
        }
        
        // 如果发现目标数在左边,就递归地从左半边进行二分搜索。
        if (target < nums[middle]) {
            return binarySearch(nums, target, low, middle - 1);
          } else {
            return binarySearch(nums, target, middle + 1, high);
        }//否则从右半边递归地进行二分搜索。
    }
    

    注意:

    • 在计算 middle 下标的时候,不能简单地用 (low + hight) / 2,可能会导致溢出。

    • 在取左半边以及右半边的区间时,左半边是 [low, middle - 1],右半边是 [middle + 1, high],这是两个闭区间。因为已经确定了 middle 那个点不是我们要找的,就没有必要再把它加入到左、右半边了。

    • 对于一个长度为奇数的数组,例如:{1, 2, 3, 4, 5},按照 low + (high - low) / 2 来计算,middle 就是正中间的那个位置,对于一个长度为偶数的数组,例如 {1, 2, 3, 4},middle 就是正中间靠左边的一个位置。

    时间复杂度是 O(logn)

    非递归解法

    非递归写法的代码模板如下。

    int binarySearch(int[] nums, int target, int low, int high) {
        // 在 while 循环里,判断搜索的区间范围是否有效
        while (low <= high) {
            // 计算正中间的数的下标
            int middle = low + (high - low) / 2;
        
    	    // 判断正中间的那个数是不是要找的目标数 target。如果是,就返回下标 middle
    	    if (nums[middle] == target) {
    	        return middle;
    	    }
        
    	    // 如果发现目标数在左边,调整搜索区间的终点为 middle - 1;否则,调整搜索区间的起点为 middle + 1
    	    if (target < nums[middle]) {
    	        high = middle - 1;
    	      } else {
    	        low = middle + 1;
    	      }
    	    }
    
    	    // 如果超出了搜索区间,表明无法找到目标数,返回 -1  
    	    return -1;
    }
    

    为什么 while 循环的条件中是 <=,而不是 < ?

    答:因为初始化 high 的赋值是 nums.length - 1,即最后一个元素的索引,而不是 nums.length。

    这二者可能出现在不同功能的二分查找中,区别是:前者相当于两端都闭区间 [left, right],后者相当于左闭右开区间 [left, right),因为索引大小为 nums.length 是越界的。

    我们这个算法中使用的是 [left, right] 两端都闭的区间。这个区间就是每次进行搜索的区间。

    例题分析

    找确定的边界

    边界分上边界和下边界,有时候也被成为右边界和左边界。确定的边界指边界的数值等于要找的目标数。

    例题:LeetCode 第 34 题,在一个排好序的数组中找出某个数第一次出现和最后一次出现的下标位置。

    示例:输入的数组是:{5, 7, 7, 8, 8, 10},目标数是 8,那么返回 {3, 4},其中 3 是 8 第一次出现的下标位置,4 是 8 最后一次出现的下标位置。

    解题思路

    在二分搜索里,把第一次出现的地方叫下边界(lower bound),把最后一次出现的地方叫上边界(upper bound)。

    那么成为 8 的下边界的条件应该有两个。

    该数必须是 8; 该数的左边一个数必须不是 8: 8 的左边有数,那么该数必须小于 8; 8 的左边没有数,即 8 是数组的第一个数。

    而成为 8 的上边界的条件也应该有两个。

    该数必须是 8; 该数的右边一个数必须不是 8: 8 的右边有数,那么该数必须大于8; 8 的右边没有数,即 8 是数组的最后一个数。

    代码实现

    用递归的方法来寻找下边界,代码如下。

    int searchLowerBound(int[] nums, int target, int low, int high) {
        if (low > high) {
            return -1;
        }
      
        int middle = low + (high - low) / 2;
        //判断是否是下边界时,先看看 middle 的数是否为 target,并判断该数是否已为数组的第一个数,或者,它左边的一个数是不是已经比它小,如果都满足,即为下边界。
        if (nums[middle] == target && (middle == 0 || nums[middle - 1] < target)) {
            return middle;
        }
    
        if (target <= nums[middle]) {
            return searchLowerBound(nums, target, low, middle - 1);
          } else {
            return searchLowerBound(nums, target, middle + 1, high);
          } //不满足,如果这个数等于 target,那么就得往左边继续查找。
    }
    

    查找上边界的代码如下。

    int searchUpperBound(int[] nums, int target, int low, int high) {
        if (low > high) {
            return -1;
        }
      
        int middle = low + (high - low) / 2;
        
        //判断是否是上边界时,先看看 middle 的数是否为 target,并判断该数是否已为数组的最后一个数,或者,它右边的数是不是比它大,如果都满足,即为上边界。    
        if (nums[middle] == target && (middle == nums.length - 1 || nums[middle + 1] > target)) {
            return middle;
        }
        
        if (target < nums[middle]) {
            return searchUpperBound(nums, target, low, middle - 1);
          } else {
            return searchUpperBound(nums, target, middle + 1, high);
          } //不满足时,需判断搜索方向。
    }
    

    找模糊的边界

    二分搜索可以用来查找一些模糊的边界。模糊的边界指,边界的值并不等于目标的值,而是大于或者小于目标的值。

    例题:从数组 {-2, 0, 1, 4, 7, 9, 10} 中找到第一个大于 6 的数。

    解题思路

    在一个排好序的数组里,判断一个数是不是第一个大于 6 的数,只要它满足如下的条件:

    该数要大于 6; 该数有可能是数组里的第一个数,或者它之前的一个数比 6 小。 只要满足了上面的条件就是第一个大于 6 的数。

    代码实现

    Integer firstGreaterThan(int[] nums, int target, int low, int high) {
        if (low > high) {
            return null;
        }
      
        int middle = low + (high - low) / 2;
        
        //判断 middle 指向的数是否为第一个比 target 大的数时,须同时满足两个条件:middle 这个数必须大于 target;middle 要么是第一个数,要么它之前的数小于或者等于 target。 
        if (nums[middle] > target && (middle == 0 || nums[middle - 1] <= target)) {
            return middle;
        }
    
    
        if (target < nums[middle]) {
            return firstGreaterThan(nums, target, low, middle - 1);
          } else {
            return firstGreaterThan(nums, target, middle + 1, high);
          }
    }
    

    对于这道题,当不满足条件,而 middle 的数等于 target 的时候怎么办?举例说明,如果要求的是第一个大于 6 的数,而数组中有多个 6 挨在一起,而此时的 middle 指向其中的一个 6,程序必须得在右半边搜索。

    旋转过的排序数组

    二分搜索也能在经过旋转了的排序数组中进行。

    例题:LeetCode 第 33 题,给定一个经过旋转了的排序数组,判断一下某个数是否在里面。

    示例:给定数组为 {4, 5, 6, 7, 0, 1, 2},target 等于 0,答案是 4,即 0 所在的位置下标是 4。

    解题思路

    对于这道题,输入数组不是完整排好序,还能运用二分搜索吗?

    由于题目说数字了无重复,举个例子:
    1 2 3 4 5 6 7 可以大致分为两类,
    第一类 2 3 4 5 6 7 1 这种,也就是 nums[start] <= nums[mid]。此例子中就是 2 <= 5。
    这种情况下,前半部分有序。因此如果 nums[start] <=target<nums[mid],则在前半部分找,否则去后半部分找。

    第二类 6 7 1 2 3 4 5 这种,也就是 nums[start] > nums[mid]。此例子中就是 6 > 2。
    这种情况下,后半部分有序。因此如果 nums[mid] <target<=nums[end],则在后半部分找,否则去前半部分找。

    代码实现

    int binarySearch(int[] nums, int target, int low, int high) {
        if (low > high) {
            return -1;
        } //判断是否已超出了搜索范围,是则返回-1。
      
        int middle = low + (high - low) / 2; //取中位数。
    
        if (nums[middle] == target) {
            return middle;
        } //判断中位数是否为要找的数
    
    
        if (nums[low] <= nums[middle]) { //判断左半边是不是排好序的。
            if (nums[low] <= target && target < nums[middle]) { //是,则判断目标值是否在左半边。
                return binarySearch(nums, target, low, middle - 1); //是,则在左半边继续进行二分搜索。
            }
            return binarySearch(nums, target, middle + 1, high); //否,在右半边进行二分搜索。
          } else {
            if (nums[middle] < target && target <= nums[high]) { //若右半边是排好序的那一半,判断目标值是否在右边。
                return binarySearch(nums, target, middle + 1, high); //是,则在右半边继续进行二分搜索。
            }
            return binarySearch(nums, target, low, middle - 1); //否,在左半边进行二分搜索。
        }
    }
    

    不定长的边界

    前面介绍的二分搜索的例题都给定了一个具体范围或者区间,那么对于没有给定明确区间的问题能不能运用二分搜索呢?

    例题:有一段不知道具体长度的日志文件,里面记录了每次登录的时间戳,已知日志是按顺序从头到尾记录的,没有记录日志的地方为空,要求当前日志的长度。

    解题思路

    可以把这个问题看成是不知道长度的数组,数组从头开始记录都是时间戳,到了某个位置就成为了空:{2019-01-14, 2019-01-17, … , 2019-08-04, …. , null, null, null …}。

    思路 1:顺序遍历该数组,一直遍历下去,当发现第一个 null 的时候,就知道了日志的总数量。很显然,这是很低效的办法。

    思路 2:借用二分搜索的思想,反着进行搜索。

    • 一开始设置 low = 0,high = 1
    • 只要 logs[high] 不为 null,high *= 2
    • 当 logs[high] 为 null 的时候,可以在区间 [0, high] 进行普通的二分搜索

    代码实现

    // 先通过getUpperBound函数不断地去试探在什么位置会出现空的日志。
    int getUpperBound(String[] logs, int high) {
        if (logs[high] == null) {
            return high;
        }
        return getUpperBound(logs, high * 2);
    }
    
    // 再运用二分搜索的方法去寻找日志的长度。
    int binarySearch(String[] logs, int low, int high) {
        if (low > high) {
            return -1;
        }
      
        int middle = low + (high - low) / 2;
      
        if (logs[middle] == null && logs[middle - 1] != null) {
            return middle;
        }
      
        if (logs[middle] == null) {
            return binarySearch(logs, low, middle - 1);
          } else {
            return binarySearch(logs, middle + 1, high);
        }
    }`
    

    最后

    微信搜索:月伴飞鱼

    1.日常分享一篇实用的技术文章,对面试,工作都有帮助

    2.后台回复666,获得海量免费电子书籍,会持续更新

    展开全文
  • 二分搜索树的基本概念 二分搜索树的基本操作 插入 删除 查询 实现二分搜索二分搜索树的不足 二分搜索树的基本概念 二分搜索树(Binary Search Tree)满足一下几个条件: 若它的左子树不为空,左子树上所有...

    本文主要包括以下内容:

    1. 二分搜索树的基本概念
    2. 二分搜索树的基本操作
      1. 插入
      2. 删除
      3. 查询
    3. 实现二分搜索树
    4. 二分搜索树的不足

    二分搜索树的基本概念

    二分搜索树(英语:Binary Search Tree),也称为 二叉查找树二叉搜索树有序二叉树(ordered binary tree)排序二叉树(sorted binary tree)

    二分搜索树(Binary Search Tree)满足以下几个条件:

    1. 若它的左子树不为空,左子树上所有节点的值都小于它的根节点
    2. 若它的右子树不为空,右子树上所有的节点的值都大于它的根节点
    3. 它的左、右子树也都是二分搜索树

    如果插入的元素在二分搜索中已经存在根据具体的情况而定,如果不允许重复, 直接抛弃即可;如果允许重复可以使用计数的方式,即每个节点保存自己的个数。

    二分搜索树有着高效的插入、删除、查询操作。平均时间的时间复杂度为 O(log n);最差情况为 O(n) ,具体原因后面会介绍。

    如下面一个二分搜索树:

    这里写图片描述

    二分搜索树的基本操作

    插入操作

    根据二分搜索树的定义,二分搜索树的插入操作就比较简单了

    如果二分搜索树为空,那么新插入的节点就作为根节点
    如果二分搜索树不为空,新节点和根节点作比较,如果比根节点小,则和根节点的左子树比较;如果比根节点大则和右子树作比较,直到没有左子树或者右子树了,然后把新节点当作左子树或者右子树节点。

    以上图的二分搜索树为例,往二分搜索树添加节点10

    首先和根节点11作比较,1011小,和11的左子树7对比,比7大,然后和7的右子树8对比,比8大,然后和8右子树对比,发现8的右子树为空,则新节点10作为8的右子树:

    二分搜索树的插入

    删除操作

    删除操作就比插入操作要稍微复杂一点,二分搜索树的删除操作一般分为以下几种情况:

    如果要删除的节点只有左子树

    如果要删除的节点只有左子树,那么直接把它的左子树代替要删除的节点即可。

    比如要删除节点3,它只有左子树:

    这里写图片描述

    删除后

    这里写图片描述

    如果要删除的节点只有右子树

    如果要删除的节点只有右子树,直接让其右子树代替要删除的节点即可。

    比如要删除节点20,它只有右子树:

    这里写图片描述

    删除后

    这里写图片描述

    如果要删除的节点同时拥有左子树和右子树

    如果要删除的节点同时又左子树和右子树,首先找到要删除节点的后继(该节点右子树中的最小值)
    然后把后继删除并且替换要删除的节点

    比如要删除下面的二分搜索树的节点20

    这里写图片描述

    然后把要删除的节点20的后继22删除并代替要删除的节点

    这里写图片描述

    也可以用待删除节点的前驱(节点的左子树中的最大值)

    这里写图片描述

    删除后

    这里写图片描述

    查询操作

    二分搜索树的查询操作和插入操作类似,也是不断的比较,前提是如果相等就不用比较了,如果不等就按照插入的方式进行比较。

    在比较的过程就把很多无用的元素过滤掉了,所以二分搜索树的插入、删除、查询是很高效的。

    实现二分搜索树

    public class BST<T extends Comparable<T>> {
    
        private static class Node<T> {
            private T value;
            private Node<T> left, right;
    
            public Node(T value) {
                this.value = value;
            }
        }
    
        private Node<T> root;
        private int size;
    
        public boolean isEmpty() {
            return size == 0;
        }
    
        public int size() {
            return size;
        }
    
        public void add(T e) {
            root = add(root, e);
        }
    
        private Node<T> add(Node<T> node, T e) {
            if (node == null) {
                size++;
                return new Node<>(e);
            }
    
            if (e.compareTo(node.value) < 0)
                node.left = _add(node.left, e);
            else if (e.compareTo(node.value) > 0)
                node.right = _add(node.right, e);
    
            return node;
        }
    
    
        public boolean contains(T e) {
            return contains(root, e);
        }
    
    
        private boolean contains(Node<T> node, T e) {
            if (node == null) {
                return false;
            }
            if (e.compareTo(node.value) < 0) {
                return contains(node.left, e);
            } else if (e.compareTo(node.value) > 0) {
                return contains(node.right, e);
            }
            return true;
        }
    
    
        /**
         * 前序遍历
         */
        public void preorder() {
            preorder(root);
        }
    
        private void preorder(Node<T> node) {
            if (node == null) {
                return;
            }
            System.out.println(node.value);
            preorder(node.left);
            preorder(node.right);
        }
    
    
        /**
         * 前序遍历的非递归实现
         */
        public void preorderNoRecurse() {
            if (root == null)
                return;
            Stack<Node<T>> stack = new Stack<>();
            stack.add(root);
            while (!stack.isEmpty()) {
                Node<T> n = stack.pop();
                System.out.println(n.value);
                if (n.right != null)
                    stack.push(n.right);
                if (n.left != null)
                    stack.push(n.left);
            }
        }
    
    	//中序遍历
        public void inorder() {
            inorder(root);
        }
    
        private void inorder(Node<T> node) {
            if (node == null) {
                return;
            }
            inorder(node.left);
            System.out.println(node.value);
            inorder(node.right);
        }
    
    
    	//后序遍历
        public void postorder() {
            postorder(root);
        }
    
        private void postorder(Node<T> node) {
            if (node == null) {
                return;
            }
            postorder(node.left);
            postorder(node.right);
            System.out.println(node.value);
        }
    
    	//广度优先遍历
        public void levelorder() {
            if (root == null)
                return;
            Deque<Node<T>> queue = new ArrayDeque<>();
            queue.addLast(root);
            while (!queue.isEmpty()) {
                Node<T> node = queue.removeFirst();
                System.out.println(node.value);
                if (node.left != null) {
                    queue.addLast(node.left);
                }
                if (node.right != null) {
                    queue.addLast(node.right);
                }
            }
        }
    
        public T getMax() {
            if (root == null) {
                throw new NoSuchElementException();
            }
            return getMax(root).value;
        }
    
        private Node<T> getMax(Node<T> node) {
            if (node.right == null) {
                return node;
            }
            return getMax(node.right);
        }
    
        public T getMin() {
            if (root == null) {
                throw new NoSuchElementException();
            }
            return getMin(root).value;
        }
    
        private Node<T> getMin(Node<T> node) {
            if (node.left == null) {
                return node;
            }
            return getMin(node.left);
        }
    
        public T removeMin() {
            T delete = getMin();
            //因为可能只有一个节点,所以需要root接收removeMin的返回值null
            root = removeMin(root);
            return delete;
        }
    
        private Node<T> removeMin(Node<T> node) {
            if (node.left == null) {
                Node<T> rightNode = node.right;
                node.right = null;
                size--;
                return rightNode;
            }
            //把要删除节点的右节点赋值给 父节点的左节点
            node.left = removeMin(node.left);
            return node;
    
        }
    
        public T removeMax() {
            T delete = getMax();
            //因为可能只有一个节点,所以需要root接收removeMin的返回值null
            root = removeMax(root);
            return delete;
        }
    
        public Node<T> removeMax(Node<T> node) {
            if (node.right == null) {
                Node<T> leftNode = node.left;
                size--;
                node.left = null;
                return leftNode;
            }
            node.right = removeMax(node.right);
            return node;
        }
    
        /**
         * 删除任意节点
         *
         * @param e
         */
        public void remove(T e) {
            root = remove(root, e);
        }
    
        private Node<T> remove(Node<T> node, T element) {
            if (node == null) {
                return null;
            }
    
            //如果要删除的节点小于当前节点,继续查询其左子树
            if (element.compareTo(node.value) < 0) {
                node.left = remove(node.left, element);
                return node;
            }
            //如果要删除的节点大于当前节点,继续查询其右子树
            if (element.compareTo(node.value) > 0) {
                node.right = remove(node.right, element);
                return node;
            }
    
            //=======要删除的节点就是当前的节点
    
            //如果要删除节点的左子树为空
            if (node.left == null) {
                Node<T> rightNode = node.right;
                node.right = null;
                size--;
                return rightNode;
            }
    
            //如果要删除节点的右子树为空
            if (node.right == null) {
                Node<T> leftNode = node.left;
                node.left = null;
                size--;
                return leftNode;
            }
    
            //=======如果要删除的节点左右子树都不为空
    
            //找到要删除节点的后继,也就是右子树的最小值
            Node<T> successor = getMin(node.right);
            successor.right = removeMin(node.right);
            successor.left = node.left;
            node.left = node.right = null;
            return successor;
        }
    
    }
    
    

    由于二分搜索树的特性,二分搜索树的中序遍历就是二分搜索树的从小到大的顺序。

    上面的二分搜索树主要是通过递归实现的,下面仅分析下add插入方法的递归:

    假设要往下面一个二分搜索树插入元素 7

    这里写图片描述

    插入操作的调用栈如下所示(为了方便描述,省略具体的栈帧细节,栈帧里的数字均表示节点):

    这里写图片描述

    这里写图片描述

    插入的最终结果如下:

    这里写图片描述

    为什么要用 root 接收 add(root,e)方法的返回值?

    public void add(T e) {
       root = add(root, e);
    }
    

    这是因为如果当前二分搜索树为空,那么新插入的节点就是根节点。如果不为空,也就是对root根节点赋值给自己。用递归的方式实现很优雅巧妙。删除操作也是类似的。

    关于递归可以的话题可以看下我之前的文章
    数据结构与算法(五)深入理解递归

    二分搜索树的不足

    在一般情况下,二分搜索树有着高效的插入、删除、查询等操作,时间复杂度为O(LogN)

    但是如果待插入的数据刚好是有序的,那么这个二分搜索树就退化成链表了,也就是为什么二分搜索树的最差时间复杂度为O(N)

    例如下面两个退化成链表的二分搜索树:

    这里写图片描述

    解决这个问题,这就是后面要介绍的平衡二叉树。


    下面是我的公众号,干货文章不错过,有需要的可以关注下,有任何问题可以联系我:
    公众号:  chiclaim

    本文相关代码

    展开全文
  • 二分搜索与三分搜索的应用

    千次阅读 2016-11-05 16:22:55
    二分搜索与三分搜索的应用: 二分和三分都利用了分治的思想,都是通过不断缩小查找的范围,把问题分解为更小的子问题直到找到解为止,,二分的时间复杂度为log2(n),而三分的时间复杂度为3log3(n),两者都是非常高效...

    二分搜索与三分搜索的应用:


    二分和三分都利用了分治的思想,都是通过不断缩小查找的范围,把问题分解为更小的子问题直到找到解为止,,二分的时间复杂度为log2(n),而三分的时间复杂度为3log3(n),两者都是非常高效的。

    在解题时经常会遇到二分法与其他算法结合的题目,因此有必要总结一下。


    一、二分搜索

    (1)、应用二分最常见或者说最基础的的就是从有序序列中查找某个值:查找等于val的位置,大于等于val的第一个位置/值,者大于val的第一个值/位置,在STL中都有相对应的实现,binary_search,Lower_bound, .upper_bound等等。

    (2)、通常我们会遇到一些问题,这个问题有单调性的特征,这时便可以使用二分了,举个例子,假设求满足某个条件的最小的x,如果对于x1>x都有x1满足条件的话,那么便可以二分求解x了。也就是说,如果问题具有的特征是,对于某个值x,x右边或者左边的值都满足或者不满足某个条件。二分常见于一些最优化问题的处理,比如说最小化最大值,最大化最小值,最大化平均值等等。

    (3)、下面是一些常见的应用,总结不可能是全面的,目的是理解二分的思想。


    1、 假定一个解并判断是否可行。          

    Poj1064 - Cable master


    题意:给出n条线段,以米的单位给出,小数点后两位(精确到厘米),要你对这些线段裁剪,裁剪出m条等长且尽量长的线段,并且让这些线段尽可能长另外线段的长度不能小于1厘米,如果筹不够m条,输出0.00

    分析:和poj3122是一样的,每次假定一个解,判断是否符合要求.对于当前假定的长度len,如果以这种方式去切割时不能满足分出m条线段来则证明len太大,解存在于左区间,否则丢弃左边的区间继续去搜索更大的len

    注意题目要求不能四舍五入,所以需要丢弃小数点两位以后的部分。

    #include <cstdio>
    #include <algorithm>
    #include <cstring>
    #include <cmath>
    
    using namespace std;
    double len[10010];
    const double EPS= 1e-6;
    
    int main()
    {
        int n, k;
        scanf("%d %d", &n, &k);
        double sum = 0;
        for (int i = 0; i < n; i++) scanf("%lf", &len[i]), sum += len[i];
        double l = 0.0, r = sum/k;
        while (r - l >= EPS){
            double m = l + (r-l)/2;
            int num = 0;
            for (int i = 0; i < n; i++) num += (int)(len[i] / m);
            num >= k ? l = m : r = m;
        }
        printf("%.2f\n", floor(r*100) / 100);
        return 0;
    }
    

    2、 二分最大化最小值

    Poj2456 - Aggressive cow


    题意:有n个牛舍,第i个牛舌在xi的位置上面,但是m头牛会互相攻击,因此要使得最近的两头牛之间的距离尽量大,求这个距离。

    分析:很明显,枚举所有可能的距离分别判断一下是否能放m头牛能得出解,但是这样复杂度太高,这时候就要思考如何高效的求解了。问题很明显具有的一个特征是:对于当前的距离x,如果x不满足条件,那么比x大的也不可能满足条件,如果满足的话,那么继续去找更大的x。所以我们就是要求出能使得两头牛之间的距离不小于d的最大的d,直接二分即可。判断函数C(x)为能够使得m头牛之间两两的距离都大于等于d。那么首先对牛舍位置排序,之后从第一个牛舍开始,贪心地放在刚好距离不小于d的另一个牛舍上,看能否放n头牛即可。

     

    #include <cstdio>
    #include <algorithm>
    #include <cstring>
    #include <cmath>
    
    using namespace std;
    int n, c;
    int x[100010];
    
    int cal(int dis)
    {
        int k = 0, cnt = 1;
        for (int i = 0; i < n; i++)
            if (x[k] + dis <= x[i]) cnt++, k = i;
        return cnt >= c;
    }
    int main()
    {
        scanf("%d %d", &n, &c);
        for (int i = 0; i < n; i++) scanf("%d", &x[i]);
        sort(x, x+n);
        int l = 0, r = x[n-1] - x[0];
        while (r - l > 1){
            int m = (r + l) / 2;
            cal(m) ? l = m : r = m;
        }
        printf("%d\n", l);
        return 0;
    }


    Poj3258 - River Hopscotch


    题意:一条宽为L的河,有n个石头,然后河的左端为位置0点,右端为位置L点,给定n个石头每个石头的位置,现在要从左端跳至河的右端,只能从一个石头跳至另一个石头上面,然后我们可以去除河中最多m个石头,求去除石头之后一次跳跃的最短距离的最大值是多少?

    分析:二分搜索距离,判断的明显就是去掉的石头的数量,跟上道题同样的思路,首先要使得每次跳跃的长度尽可能大的话,那么我们需要去掉尽可能去掉多的石头。那么采取贪心的策略,对于当前假定的距离d,从河的左端开始,每次把离当前的石头的距离小于d的全部去掉,然后跳至刚距离刚好大于d的那个石头,这样一直判断下去直到跳至河的右端,采取这样的贪心策略所跳的次数一定最多,然后去掉的石头数量当然也是最少的,如果此时去掉的石头数量仍然大于m的话,证明这个距离d不可行,而且比d大的也绝对不可行,所以缩小d,否则的话增大d。一直二分直到找到最大的可能的d为止。

    可是对于这样的做法,我感觉有一个问题就是:对于当前的距离d,如果按这样的贪心策略来跳的话,会不会导致在要跳至河的右端的最后一次跳跃的时候距离小于d,那么这不就不满足大于等于d的条件了吗?现在还没有想明白这个问题表示有点难以理解,但是这样做可以A,是我想错了吗?

     

    #include <cstdio>
    #include <algorithm>
    #include <cstdio>
    using namespace std;
    
    int x[50010];
    int n, l, m;
    typedef long long LL;
    const int INF = 0x3f3f3f3f;
    
    int cal(int d)
    {
        int cnt = 0, last = 0;
        for (int i = 1; i <= n; i++){
            if (x[i] - x[last] < d)  cnt++;
            else last = i;
        }
        return cnt <= m;
    }
    int main()
    {
        scanf("%d %d %d", &l, &n, &m);
        for (int i = 1; i <= n; i++) scanf("%d", x+i);
        sort(x+1, x+n+1);
        x[0] = 0, x[++n] = l;
        int le = 0, ri = l+10;
        while (ri - le > 1){
            int m = ri- (ri-le)/2;
            if (cal(m))  le = m;
            else ri = m;
        }
        printf("%d\n", le);
        return 0;
    }
    


    3、 最大化平均值

    Poj2976 - Dropping tests


    题意:n场考试,i场考试有bi,然后得的分数是ai分,最后得的平均分是ai的和除以bi的和乘以100,最多可以去掉k场考试,求去掉k场考试之后平均分最大能多少?

    分析:像这种题首先都会想到贪心法求解,但是局部最优不能保证整体最优,贪心策略是错误的,只能另寻他路,一般还需要是分析抓住题目的特征然后以此入手。

    满足单调性特征的题目都可以尝试二分搜索,很明显这个题可以二分,二分的最主要一步是确定判断的函数C(x),这题中需要判断的是对于当前假定的平均分x,如何判断是否能达到呢?题目中的变量有两个,可以把两者变成一者来判断。那么求出每个ai-bi*x,如果最大的n-k个相加大于等于0的话证明可行,且继续搜索更大的平均分,否则不可能达到x的平均分,应缩小解的范围。根据上面的原则就可以进行求解了。

     

    #include <cstdio>
    #include <algorithm>
    #include <cstring>
    #include <numeric>
    #define EPS 1e-5
    using namespace std;
    
    const int INF = 0x3f3f3f3f;
    typedef long long LL;
    const int N = 1010;
    int n, k;
    int a[N], b[N];
    double t[N];
    
    int main()
    {
        while (scanf("%d %d", &n, &k), n || k){
            for (int i = 0; i < n; i++) scanf("%d", a+i);
            for (int i = 0; i < n; i++) scanf("%d", b+i);
            double r = 1.0, l = 0.0;
            while (r - l >= EPS){
                double m = r - (r-l)/2;
                for (int i = 0; i < n; i++) t[i] = a[i] - m*b[i];
                sort(t, t + n);
                if (accumulate(t + k, t + n, 0.0) >= 0.0) l = m;
                else r = m;
            }
            printf("%d\n", (int)(l*100 + 0.5));
        }
        return 0;
    }
    



    4、二分查找第k

    Poj3579 – Median


    题意:有n个数组成的一个序列,对于∣Xi - Xj (1≤ i  j ≤ N),这样的数总共C(N,2)个,求出值处在最中间的那个数。

    分析:直接枚举所有的差值明显不可能,时间复杂度过高。二分搜索最基本的应用便是查找一个序列中的某个值,查找第k大只是一个拓展而已,判断的原则显而易见就是比差值比他大的有Cn,2/2个,为方便进行判断,首先对序列进行排序,对于当前假定的某个值x,因为数据量比较大,直接二分查找,也只要循环一遍,统计大于等于a[i]+x的元素有多少个,就可以进一步确定解的范围了。

     

    #include <cstdio>
    #include <algorithm>
    #include <cstring>
    #define INF 0x3f3f3f3f
    #define LL long long
    using namespace std;
    
    int n;
    int a[100010];
    LL tot;
    
    int cal(int k)
    {
        LL cnt = 0;
        for (int i = 0; i < n; i++) cnt += a+n - lower_bound(a+i, a+n, a[i]+k);
        return cnt > tot;
    }
    int main()
    {
        while (~scanf("%d", &n)){
            for (int i = 0; i < n; i++) scanf("%d", a+i);
            sort(a, a + n);
            int l = 0, r = a[n-1]-a[0]+10;
            tot = n*(n-1) / 4;
            while (r - l > 1){
                int m = r - (r-l)/2;
                if (cal(m)) l = m;
                else r = m;
            }
            printf("%d\n", l);
        }
        return 0;
    }


    5、二分最小化最大值

    Poj3662 - Telephone Lines


    题意:john需通过n根电线杆建立一个电话线系统把农庄连接到电信公司,这些电线杆从1n编号,1号已连接到电话公司,n号就是john的农庄,现在有p对电线杆之间是可以用电缆连接的,然后电信公司可以提供k条电缆,其他的由John提供,求john提供的电缆中最长的那根的长度最短是多少。

    分析:直接枚举显然不可能。最小化最大值是一个常见的最值优化目标。问题具有的特征是单调性。长度越长,越可能达成,长度越短,越不可能达成。我们只需要通过二分不断来枚举当前的长度就行了。如何判断当前的长度是否可行呢?题目给定了一个明显的图,点数和边的情况都已输入,如果从1号连接到n号需要的最少的电缆的数量仍然大于k的话,证明当前的长度太短,不可能保证联通,否则继续去搜索尽量短的长度。那么我们只需要找出保证1n号联通的最少电缆数量就好了,如何判断呢?利用动态规划的思想求取最短路就好了,图中所有长度大于等于当前假定的长度的边定为边权1,否则定为边权0,这样就可以求取最少需要多少根电缆了。

     

    #include <cstdio>
    #include <algorithm>
    #include <cstring>
    #include <queue>
    #include <vector>
    #include <utility>
    using namespace std;
    
    typedef pair<int, int> p;
    const int INF = 0x3f3f3f3f;
    typedef long long LL;
    struct edge{
        int to, d;
        edge(int a = 0, int b = 0) : to(a), d(b){}
    };
    vector<edge> G[1010];
    int dis[1010];
    
    int dijstra(int n, int len)
    {
        fill(dis + 2, dis+ n+1, INF);
        priority_queue<p, vector<p>, greater<p> > q;
        q.push(p(0, 1));
        while (!q.empty()){
            p t = q.top(); q.pop();
            int x = t.second;
            if (dis[x] < t.first) continue;
            if (x == n) return dis[n];
            for (int i = 0; i < G[x].size(); i++){
                int to = G[x][i].to, d = G[x][i].d;
                d = d <= len ? 0 : 1;
                if (dis[to] > dis[x] + d){
                    dis[to] = dis[x] + d;
                    q.push(p(dis[to], to));
                }
            }
        }
        return INF;
    }
    int main()
    {
        int n, k, p, ma = 0;
        scanf("%d %d %d", &n, &p, &k);
        for (int i = 0; i < p; i++){
            int f, t, d;
            scanf("%d %d %d", &f, &t, &d);
            ma = max(ma, d);
            G[f].push_back(edge(t, d));
            G[t].push_back(edge(f, d));
        }
        int l = -1, r = ma + 1;
        while (r - l > 1){
            int m = (r+l) / 2;
            dijstra(n, m) <= k ? r = m : l = m;
        }
        r > ma? puts("-1") : printf("%d\n", r);
        return 0;
    }


    (4)、二分搜索的总结:

    1使用二分需要保证上下界包含解的所有范围,不管是最优化问题还是判定问题,最重要的一步都是向判定问题C(x)的转化,即判断当前假定的解是否符合条件。

    2、对于整数的二分,循环条件while (r – l) > 1)或者while (r >= l)都可以,怎么方便怎么处理,只要保证那个不是解的端点在初始化时不取可能的解就行了。对于小数的二分,可以用eps来控制,但是精度的控制必须满足条件而且不能取得太小,否则容易进入死循环。可以循环一定的次数来二分,而不通过while (r – l) > EPS)来循环。一般循环100次就可以达到1e-30的精度了。而且最后得到的解就是其中的一个端点的值,是哪个端点就看二分的方式了。

    正因为二分的高效和简单,所以二分常与其他算法结合起来,应用也十分普遍。掌握二分的思想是很重要的。

     



    二、三分搜索


    二分法适用于单调函数求解某点的值,而三分法适用于拟凸函数求解极值。

     

    三分与二分的实现时的不同点在于每次会在lr之间选取两个点,分别是:m = l+(r-l)/3=(2l+r)/3 mm = r-(r-l)/3=(l+2r)/3,假设判定函数为c(x),c(m)>c(mm)时证明m更靠近最值点,则令r = mm,否则令l = mm。如果要求取的是极小值,则上面的改为小于即可。


    下面是一些三分搜索的常见应用:

    1、三分角度


    题意:给定n个点,求最小的正方形能够覆盖这n个点,正方形不需要平行坐标轴。输出这个正方形的面积。

    分析:一般随角度变化的值都会具有凸函数的性质,极值点总在某点取得。可以知道,不论正方形的角度如何,最小的正方形两条对边上面至少一定会经过一个点,否则总可以把正方形缩小而且也满足条件。

    所以我们可以三分正方形的边与x轴正向的夹角a,然后求出旋转坐标系a角之后横坐标和纵坐标的最大值和最小值之差,然后要保证覆盖所有点,取两个坐标的差的较大值即为边长。


    #include <cstdio>
    #include <algorithm>
    #include <cstring>
    #include <cmath>
    #define INF 0x3f3f3f3f
    #define LL long long
    #define EPS 1e-8
    using namespace std;
    
    int x[50], y[50];
    int n;
    double cal(double a)
    {
        double maxx = -INF, maxy = -INF, minx = INF, miny = INF;
        for (int i = 0; i < n; i++){
            double xx = x[i]*cos(a) - y[i]*sin(a);
            double yy = y[i]*cos(a) + x[i]*sin(a);
            maxx = max(maxx, xx);
            maxy = max(maxy, yy);
            minx = min(minx, xx);
            miny = min(miny, yy);
        }
        return max(maxx - minx, maxy - miny);
    }
    int main()
    {
        int t;
        scanf("%d", &t);
        while (t--){
            scanf("%d", &n);
            for (int i = 0; i < n; i++) scanf("%d %d", x+i, y+i);
            double l = 0, r = acos(-1.0);
            while (r - l >= EPS){
                double m = l + (r-l)/3, mm = r - (r-l)/3;
                if (cal(m) <= cal(mm)) r = mm;
                else l = m;
            }
            printf("%.2f\n", cal(l) * cal(l));
        }
        return 0;
    }


    2、三分坐标

    Poj2420 - A Star not a Tree?

     

    题意:二维坐标平面上有n个点,求出一个点使得到这n点的距离之和最小。

    分析:只能尝试搜索的解法了。可以知道极值点一定位于这n点当中,怎么求解极值点呢?距离不满足单调性,可以尝试三分搜索极值点。对于两个量同时变化的情况,可以固定一者,枚举另一者求取最优解,那么在这里我们可以进行两次三分,首先三分横坐标x,然后对于每个假定的x,三分搜索当前横坐标下要取得最优值纵坐标应取的值。

    #include <cstdio>
    #include <algorithm>
    #include <cstring>
    #include <cmath>
    #define INF 0x3f3f3f3f
    #define LL long long
    #define EPS 1e-2
    using namespace std;
    
    int n;
    int x[110], y[110];
    double maxx, maxy;
    
    double dis(double xx, double yy)
    {
        double sum = 0;
        for (int i = 0; i < n; i++) sum += sqrt((x[i]-xx)*(x[i]-xx) + (y[i]-yy)*(y[i]-yy));
        return sum;
    }
    double cal(double y)
    {
        double l = 0, r = maxx;
        while (r - l >= EPS){
            double m = l + (r-l)/3, mm = r - (r-l)/3;
            if (dis(m, y) - dis(mm, y) <= -EPS) r = mm;
            else l = m;
        }
        return dis(l, y);
    }
    int main()
    {
        scanf("%d", &n);
        for (int i = 0; i < n; i++) scanf("%d %d", x+i, y+i);
        maxx = *max_element(x, x+n), maxy = *max_element(y, y+n);
        double l = 0, r = maxy;
        while (r - l >= EPS){
            double m = l + (r-l)/3, mm = r - (r-l)/3;
            if (cal(m) - cal(mm) <= -EPS) r = mm;
            else l = m;
        }
        printf("%.0f\n", cal(l));
        return 0;
    }


    3、三分边长

    Poj3737 – UmBasketella

     

    题意:给出一个圆锥的表面积(侧面积+底面积),求圆锥的最大体积。

    分析:三分的入门题,体积关于半径满足凸函数的性质,直接三分底面圆的半径长度就可以了。圆锥的体积公式根据S推导下就可以了。

     

    #include <cstdio>
    #include <algorithm>
    #include <cstring>
    #include <cmath>
    
    using namespace std;
    double S, r, V, h;
    const int INF = 0x3f3f3f3f;
    typedef long long LL;
    const double PI = acos(-1);
    const double EPS = 1e-4;
    
    double cal(double r)
    {
        h = sqrt(pow((S - PI*r*r) / (PI*r), 2) - r*r);
        return V = PI/3.0 * r*r*h;
    }
    int main()
    {
        while(~scanf("%lf", &S)){
            double l = 0, r = sqrt(S / PI);
            for (int i = 0; i < 50; i++){
                double m = (2*l + r) / 3,  mm = (l + 2*r) / 3;
                cal(m) < cal(mm) ? l = m : r = mm;
            }
            printf("%.2f\n%.2f\n%.2f\n", V, h, l);
        }
        return 0;
    }
    

    4、三分距离

    SGU 204/ZOJ2340 Little jumper

    Andrew AndrewStankevich’sContest #2 @ACDream D


    题意:一只青蛙从给定的ds点出发,首先越过第一面墙上的洞跳至两面墙的中间某一点,然后从该点出发继续越过第二个洞跳至给定的df点,问要完成这次任务两次起跳的速度中的较大值最小是多少?

    分析:这题比前面之前几个题要难些了,感觉值得一做,结合了物理知识和数学分析能力还有三分搜索的方法。(感觉做了之后高中的物理平抛运动学公式全部复习了一遍….

    首先:对于一次运动,由相应的运动学公式推导可知速度为45度时一定为最小的时候:设水平速度为Vx,竖直速度为Vy,从起跳点到落地点的水平距离为X,那么Vx*Vy=g*X/2,那么当Vx=Vy时速度最小,求得这个时候到达墙壁时的高度,若越过则速度为sqrt(g*x);

    如果碰到墙壁,要使得速度尽量小,那么当高度大于洞上方高度则求得高度恰好为t时的速度,如果小于洞下方高度b的时候求得高度恰好为b时的速度。然后,对于两次运动,我们求得两个最小的速度并取其较大者就行了。但是因为速度关于落地点的函数属于凹性函数,我们可以三分查找逼近求解速度的值。

    #include <cstdio>
    #include <algorithm>
    #include <cstring>
    #include <string>
    #include <cmath>
    #define LL long long
    #define INF 0x3f3f3f3f
    using namespace std;
    
    const double EPS = 1e-6;
    double b1, t1, b2, t2, l, ds, df, g;
    double check(double b, double t, double x, double s)
    {
        double h = s - s*s/x;
        if (b <= h && h <= t) return g*x;
        if (h > t) h = t;
        if (h < b) h = b;
        double Vx2 = g*s*(x-s) *0.5 / h;
        return Vx2 + g*g*x*x / (4*Vx2);
    }
    double MAX(double a)
    {
        return max(check(b1, t1, a + ds, ds), check(b2, t2, l-a + df, l-a));
    }
    int main()
    {
        while (~scanf("%lf %lf %lf %lf %lf %lf %lf %lf", &b1, &t1, &b2, &t2, &l, &ds, &df, &g)){
            double m, mm, le = 0, ri = l;
            int i = 0;
            while (++i <= 100){
                m = le + (ri-le)/3, mm = ri - (ri-le)/3;
                MAX(m) - MAX(mm) < -EPS? ri = mm : le = m;
            }
            printf("%.4f\n", sqrt(MAX(le)));
        }
        return 0;
    }
    


    关于三分搜索的总结:

    1、三分应用于最优化问题的求解。在解题时没必要给出证明,只要知道问题不满足单调性,就可以尝试用三分搜索极值点,而且三分整数很少见,因为除非能够证明这种策略是正确的(即完全符合凸函数的性质,但是通常极值点不会在整点取得,如果三分整数,那么函数也不是连续的了),否则很可能会错误,而三分应用在小数中是最常见的,比如说三分角度,三分坐标等等。

    2、三分搜索经常应用在数值计算的最优化问题中,对于凸函数极值的计算常常是行之有效的。注意取的两个点最好写成m = (2*l + r) / 3,  mm = (l + 2*r) / 3;而不要写成m = (r+l)/2, mm = (r+m)/2.上面的这题写成后面的那种就会错。同样的,二分最好写成m = l + (r-l)/2;


    关于三分与二分的总结就到这里,上面所述的只是自己对于两种搜索查找方式的一点点理解而已,也算是一个总结,我相信凡事总结下总是好的,这样才能收获更多,真正要做到对各种算法运用自如还是需要我们勤加练习。

    坚持总会有绽放的一天,加油~

    展开全文
  • 二分搜索相关算法题汇总

    千次阅读 2020-06-07 18:20:11
    二分搜索简介 在计算机科学中,二分搜索(binary search)也称折半搜索(half-interval search)、对数搜索(logarithmic search),是在有序数组中查找某一特定元素的搜索算法。 二分搜索是一种在每次比较之后将...
  • 二分搜索法 简介步骤 简介 二分搜索(英语:binary search),是一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜索过程结束;如果某一特定元素...
  • 搜索之线性搜索和二分搜索

    千次阅读 2017-02-04 22:45:48
    今天介绍下搜索的方法,其实对于今天介绍的两种搜索方式是很简单的,尤其是线性搜索,但是本着完整性的心态,还是不想把搜索这章中两种简单的方法漏掉,那就稍微简单介绍下吧。 注意:本博文介绍的搜索都是不含重复...
  • 二分搜索树的层序遍历

    万次阅读 2019-03-10 21:32:19
    二分搜索树的层序遍历,即逐层进行遍历,即将每层的节点存在队列当中,然后进行出队(输出节点)和入队(存入下一层的节点)的操作,以此达到遍历的目的 import java.util.LinkedList; import java.util.Queue; /** * @...
  • 二分搜索有很多写法,在算法分析与设计中,二分搜索是在递归分治这一章讲到的,所以用递归实现一下。 二分搜索其实很容易理解,设想一根从北京到上海的电线坏掉了,但是不知道是从哪里坏的,要怎样才能使用最少的...
  • 二分搜索算法的实现详解

    千次阅读 2019-03-25 15:42:51
    二分查找算法实现 问题引入:聚会上猜数,大家为了缩短游戏进程,增加游戏刺激度,往往会采用“猜中间数”的方法,不断取中间数来使得猜数范围快速缩小,而二分算法就是基于这样的思想(不是事例) 关于...
  • 关于二分查找和二分搜索

    千次阅读 2018-03-12 15:47:27
    首先是二分查找,举个有序的整数数组例子(二分查找和搜索都是针对有序数组) public int rank(int key, int n) { int lo = 0, hi = n - 1; while (lo &lt;= hi) { int mid = lo + ((hi - lo) &gt;&...
  • 分治算法(一)二分搜索技术

    千次阅读 2019-01-05 13:04:08
    2.用二分搜索技术玩猜数字游戏 2.1问题描述 假如你女朋友想跟你玩一个游戏,说:“亲爱的,猜一下我心里想的是哪个数字?这个数字在1~10范围内。”你可能会猜1,女朋友说:“小了。”接着你猜2,女朋友说:“小了...
  • 【算法】二分搜索方法

    万次阅读 多人点赞 2020-11-08 23:18:00
    【算法】二分搜索方法 二分搜索法运用了分治策略。给定已经排好序的n个元素,在这个n个元素中查找一个特定的元素x。 二分搜索法的基本思想是将n个元素分成个数大致相同的两半,取arr[n/2]与x进行比较。如果x=arr...
  • 二分搜索树的遍历

    万次阅读 2020-02-13 11:12:43
    1、前序遍历 中->... //二分搜索树的前序遍历 public void preOrder() { preOrder(root); } //前序遍历以node为根的二分搜索树,递归算法 private void preOrder(Node node) { if (node == null) {...
  • 二分搜索(查找)方法

    千次阅读 2017-04-26 08:49:10
    在讨论二分搜索方法前先说下顺序搜索:顺序搜索 将关键字key顺序地与数组中每个元素进行比较,这个过程一直持续下去,直至关键字与某个元素匹配,或者所有数组元素都已比较完毕。 int linearSearch(int list[],...
  • 特点 动态数据结构 是一颗二叉树 二分搜索树的每个节点的值: ...每个节点的值都大于其左子树的所有节点的值 每个节点的值都小于其右子树的...一般二分搜索树不包含重复元素, 当然也可以定义包含重复元素的二分...
  • C语言实现二分搜索算法

    千次阅读 2018-06-15 20:15:13
    引言: 这是我写的第一篇关于算法的...下面是分治法求解的一个经典问题“二分搜索算法”。题目: 给定已按升序排好序的n个元素a[0:n-1],现要在这n个元素中找出一特定元素x。分析:二分搜索算法(折半查找法)是...
  • 二分搜索 设a[0:n-1]是一个已排好序的数组。请改写二分搜索算法,使得当搜索元素x不在数组中时,返回小于x的最大元素的位置I和大于x的最大元素位置j public static int binarySearch(int []a,int x,int n) {int ...
  • 最优二分搜索树问题 对于一个给定的序列,{b0,a1,b1……an,bn},其中a1,a2……an是实节点,b0,b1,b2……bn是虚节点(就是二分搜索树最终找不到实节点的范围),如何找出并构建一个总耗费最小的二分搜索树? ...
  • 二分搜索树的删除节点操作

    千次阅读 多人点赞 2017-12-23 21:50:45
    本节我们来讨论一下对二叉搜索树的删除节点操作。 首先,我们先来研究一下稍微简单一点的问题,如何删除二叉树中的最小值和最大值。 例如上图的这一棵二叉树中,最小值节点和最大值节点都在哪里呢?我们可以很清楚...
  • 选择排序&二分搜索

    千次阅读 2020-01-24 16:18:49
    C语言实现选择排序和二分搜索
  • 算法设计--改写二分搜索算法

    千次阅读 2019-03-01 09:20:08
    设a[0:n-1]是已排好序的数组,请改写二分搜索算法,使得当x不在数组中时,返回小于x的最大元素位置i和大于x的最小元素位置j。当搜索元素在数组中时,i和j相同,均为x在数组中的位置。 代码: #include&lt;...
  • java实现二分搜索

    千次阅读 2020-03-14 23:02:59
    1.二分搜索树定义 二分搜索树是一个二叉树 二分搜索树的节点的值大于左子树,小于右子树的值 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-FAbuFGnW-1584198154042)(en-resource://...
  • 改写二分搜索算法

    千次阅读 2017-11-27 20:49:22
    改写二分搜索算法 2. 问题描述 设a[0:n-1]是已排好序的数组,请改写二分搜索算法,使得当x不在数组中时,返回小于x的最大元素位置i和大于x的最小元素位置j。当搜索元素在数组中时,i和j相同,均为x在数组中的位置...
  • 删除二分搜索树的任意元素

    千次阅读 2019-10-05 21:17:33
    删除二分搜索树的任意元素
  • 算法:改写二分搜索算法

    千次阅读 2017-09-27 19:16:50
    设a[0:n-1]是已排好序的数组,请改写二分搜索算法,使得当x不在数组中时,返回小于x的最大元素位置i和大于x的最小元素位置j。当搜索元素在数组中时,i和j相同,均为x在数组中的位置。问题来源:题目来源:《计算机...
  • 二分搜索算法(Java代码实现)

    千次阅读 2018-03-06 19:03:23
    二分搜索算法(Java代码实现)(1)判断是否适合分治法实现(2)实现二分搜索的Java代码如下:public class Main { public static void main(String[] args) { int[] arr = { 11, 22, 33, 44, 55, 66, 77 }; ...
  • 深入理解二分搜索树的前中后序遍历
  • C#文本框中如何编写二分搜索?如何二分搜索文本框?二分搜索的C#怎么写?
  • 2-3 改写二分搜索算法

    千次阅读 2018-03-25 15:20:45
    请改写二分搜索算法,使得当搜索元素 x 不在数组中时,返回小于 x 的最大元素的位置 i 和大于 x 的最小元素位置 j。当搜索元素在数组中时,i 和 j 相同,均为 x 在数组中的位置。测试数据(自己写的):61234567输出...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 575,885
精华内容 230,354
关键字:

二分搜索