Java教程

二分搜索各种情况总结

本文主要是介绍二分搜索各种情况总结,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

目录

      • 1. 基本的二分搜索(递归实现)
      • 2. 基本的二分搜索(非递归实现)
      • 3. 二分搜索另一种方式的区间范围
      • 4. upper 问题
      • 5. ceil 问题
      • 6. lower_ceil
      • 7. lower
      • 8. lower_floor
      • 9. upper_floor

1. 基本的二分搜索(递归实现)

  • 问题:查找目标元素,存在返回索引,不存在返回 -1

    let array = [1,2,3,4,5,6,7] 
    
    target = 3
    
  • 搜索范围:[ l, r ]

  • 递归的终止条件:

    l > r
    
  • 递归代码:

    function BinarySearch(arr, l, r, target) {
    
      if (l > r) return -1 // 递归的终止条件
    
      let mid = Math.floor(l + (r - l) / 2)
    
      if (arr[mid] === target) return mid
      if (arr[mid] < target) {
        return BinarySearch(arr, mid + 1, r, target)
      }
      return BinarySearch(arr, l, mid - 1, target)
    }
    
    let array = [1, 2, 3, 4, 5, 6, 7]
    
    console.log(BinarySearch(array, 0, array.length - 1, 1)); // 0
    console.log(BinarySearch(array, 0, array.length - 1, 3)); // 2
    

2. 基本的二分搜索(非递归实现)

  • 循环的终止条件:

    l > r (此时查找的区间为空区间)
    
  • 搜索范围:

    在 arr[l, r]范围内查找 target(变成空区间的时候退出循环)
    
  • 非递归代码:

    /*
     * @Description: 二分搜索的非递归实现
     * @Autor: zhangbing
     * @Date: 2021-09-19 11:43:30
     * @LastEditors: zhangbing
     * @LastEditTime: 2021-09-19 11:54:17
     */
    
    function binarySearch(arr, target) {
      let l = 0
      let r = arr.length - 1
    
      // 在 arr[l, r]范围内查找 target(变成空区间的时候退出循环)
      while (l <= r) {
        let mid = Math.floor(l + (r - l) / 2)
        if (arr[mid] === target) return mid
        if (arr[mid] < target) {
          l = mid + 1
        } else {
          r = mid - 1
        }
      }
    
      return -1
    }
    
    let array = [1, 2, 3, 4, 5, 6]
    console.log(binarySearch(array, 2)); // 1
    console.log(binarySearch(array, 7)); // -1
    
    

3. 二分搜索另一种方式的区间范围

  • 循环的终止条件

    l == r (因为左闭右开, 因此此时为空区间)
    
  • 搜索范围:

    在 arr[l, r) 的范围内查找 target
    
  • 代码:

    /*
     * @Description: 二分搜索另一种方式的区间范围
     * @Autor: zhangbing
     * @Date: 2021-09-19 12:05:45
     * @LastEditors: zhangbing
     * @LastEditTime: 2021-09-19 13:56:04
     */
    function binarySearch(arr, target) {
      let l = 0
      let r = arr.length // 右边开区间
    
      // 在 arr[l, r) 的范围内查找 target
      while(l < r) {
        let mid = Math.floor(l + (r - l) / 2) 
        if(arr[mid] === target) return mid
        if(arr[mid] < target) {
          l = mid + 1 // 继续在 arr[mid+1, r) 范围内寻找解
        } else {
          r = mid // 继续在 data[l, mid) 范围内寻找解
        }
      }
    
      return -1
    }
    
    let array = [1,2,3,4,5,6]
    console.log(binarySearch(array, 2)) // 1
    console.log(binarySearch(array, 7)) // -1
    

4. upper 问题

  • 问题:

    查找大于 target 的最小值(索引)
    
  • 搜索范围:

    在 arr[l,r) 的范围内查找
    
  • 代码:

    /*
     * @Description: 查找大于 target 的最小值(upper问题)
     * @Autor: zhangbing
     * @Date: 2021-09-19 12:41:50
     * @LastEditors: zhangbing
     * @LastEditTime: 2021-09-19 13:00:49
     */
    
    function binarySearch(arr, target) {
      let l = 0
      let r = arr.length // 因为大于target的最小值的索引可能超过数组的最大索引
      // 在 arr[l,r) 的范围内查找
      while (l < r) {
        let mid = Math.floor(l + (r - l) / 2)
        if (arr[mid] > target) {
          r = mid
        } else {
          l = mid + 1
        }
      }
      return l // 或者 r 也可以,因为此时 l === r
    }
    
    let array = [23, 56, 65, 69, 72, 89, 96, 99]
    console.log(binarySearch(array, 60)); // 2
    console.log(binarySearch(array, 10)); // 0
    console.log(binarySearch(array, 100)); // 8
    
    let arr = [1,2,3,3,5,5]
    console.log(binarySearch(arr, 4)); // 4
    console.log(binarySearch(arr, 3)); // 4
    
    

5. ceil 问题

  • 问题:

    若数组中不存在 target, 返回 upper
    若数组中存在 target, 返回最大索引(可能存在多个相同的值,返回最后一个值的索引)

  • 搜索范围:

    因为不存在需返回 upper,可能超出数字的最后一个元素的索引
    所以搜索范围为:arr[l, r)

  • 代码:

    /*
     * @Description: 如果数组中存在元素,返回最大索引;如果数组中不存在元素,返回 upper(大于target的最小值的索引)
     * @Autor: zhangbing
     * @Date: 2021-09-19 13:11:35
     * @LastEditors: zhangbing
     * @LastEditTime: 2021-09-19 13:24:18
     */
    
    function binarySearch_ceil(arr, target) {
      let l = 0
      let r = arr.length
      while (l < r) {
        let mid = Math.floor(l + (r - l) / 2)
        if (arr[mid] > target) {
          r = mid
        } else {
          l = mid + 1
        }
      }
    	
      // 上述代码得到的 l === r (upper的情况)
      // 判断数组是否存在 target(若存在 target ,则必然是 arr[l] 的前一个元素)
      return arr[l - 1] === target ? l - 1 : l
    }
    
    let array = [1, 1, 3, 3, 5, 5, 7, 7]
    console.log(binarySearch_ceil(array, 5)); // 5
    console.log(binarySearch_ceil(array, 6)); // 6 
    console.log(binarySearch_ceil(array, 8)); // 8
    
    

6. lower_ceil

  • 问题:

    大于等于 target 的最小索引

  • /*
     * @Description: 大于等于 target 的最小索引
     * @Autor: zhangbing
     * @Date: 2021-09-19 13:23:50
     * @LastEditors: zhangbing
     * @LastEditTime: 2021-09-19 21:54:11
     */
    
    function binarySearch_lower_ceil(arr, target) {
      let l = 0
      let r = arr.length
      while (l < r) {
        let mid = Math.floor(l + (r - l) / 2)
        if (arr[mid] < target) {
          l = mid + 1
        } else {
          r = mid
        }
      }
    
      return l
    }
    
    let array = [1,1,3,3,5,5,7,7]
    console.log(binarySearch_lower_ceil(array, 6)); // 6
    console.log(binarySearch_lower_ceil(array, 5)); // 4
    console.log(binarySearch_lower_ceil(array, 1)); // 0
    console.log(binarySearch_lower_ceil(array, 8)); // 8
    
    let array1 = [1,2,3,5,5,7,8]
    console.log(binarySearch_lower_ceil(array1, 5)); // 3
    console.log(binarySearch_lower_ceil(array1, 6)); // 5
    
    

7. lower

  • 问题:

    lower: 查找 小于 target 的最大值 (注意死循环问题,调整 mid 上取整)

  • 代码:

    /*
     * @Description: lower: 查找 小于 target 的最大值 (注意死循环问题,调整 mid 上取整)
     * @Autor: zhangbing
     * @Date: 2021-09-19 14:10:35
     * @LastEditors: zhangbing
     * @LastEditTime: 2021-09-19 14:32:07
     */
    
    function binarySearch_lower(arr, target) {
      let l = -1
      let r = arr.length - 1
      // 在 arr[l, r] 范围内寻找
      while (l < r) {
        let mid = Math.floor(l + (r - l) / 2) + 1 // 当 l 与 r 相邻时取右边界(上取整)
        if (arr[mid] < target) {
          l = mid
        } else {
          r = mid - 1
        }
      }
    
      return l
    }
    
    let array = [1, 1, 3, 3, 5, 5]
    console.log(binarySearch_lower(array, 3)) // 1
    console.log(binarySearch_lower(array, 1)) // -1
    console.log(binarySearch_lower(array, 5)) // 3
    console.log(binarySearch_lower(array, 6)) // 5
    
    let array1 = [1,3,5,7]
    console.log(binarySearch_lower(array1, 6)) // 2
    console.log(binarySearch_lower(array1, 0)) // -1
    console.log(binarySearch_lower(array1, 9)) // 3
    console.log(binarySearch_lower(array1, 5)) // 1
    
    
  • 注意:

    当 l = 0, r = 1 时,此时 mid 计算为 0,arr[mid] < target, l 会始终等于0,此时程序会陷入死循环。为避免这种情况, mid 设置为 向上取整。

8. lower_floor

  • 问题:

    lower_floor : 如果数组中存在元素,返回最小索引;如果不存在,返回 lower(小于 target 的最大值的索引)

  • 代码:

    /*
     * @Description: lower_floor : 如果数组中存在元素,返回最小索引;如果不存在,返回 lower(小于 target 的最大值的索引)
     * @Autor: zhangbing
     * @Date: 2021-09-19 14:34:46
     * @LastEditors: zhangbing
     * @LastEditTime: 2021-09-19 22:33:05
     */
    
    function binarySearch_lower_floor(arr, target) {
      let l = -1
      let r = arr.length - 1
      while (l < r) {
        let mid = Math.floor(l + (r - l) / 2) + 1
        if (arr[mid] < target) {
          l = mid
        } else {
          r = mid - 1
        }
      }
    
      if (arr[l + 1] !== target) {
        return l
      } else {
        return l + 1
      }
    
    
    }
    
    let array = [1, 1, 3, 3, 5, 5]
    console.log(binarySearch_lower_floor(array, 3)); // 2
    console.log(binarySearch_lower_floor(array, 4)); // 3
    console.log(binarySearch_lower_floor(array, 6)); // 5
    
    let array1 = [1,3,5,7,9]
    console.log(binarySearch_lower_floor(array1, 3)); // 1
    console.log(binarySearch_lower_floor(array1, 4)); // 1
    console.log(binarySearch_lower_floor(array1, 0)); // -1
    console.log(binarySearch_lower_floor(array1, 10)); // 4
    
    

9. upper_floor

  • 问题:

    如果数组中存在元素,返回最大索引;如果数组中不存在元素,返回 lower(小于 target 的最大值的索引)

  • 代码:

    /*
     * @Description: 如果数组中存在元素,返回最大索引;如果数组中不存在元素,返回 lower
     * @Autor: zhangbing
     * @Date: 2021-09-19 14:37:46
     * @LastEditors: zhangbing
     * @LastEditTime: 2021-09-19 22:47:03
     */
    
    /** <= target 的最大索引
     * [1,1,3,3,5,5]
     * 如果查找 5,返回 5
     * 如果查找 4,返回 3
     */
    
    function binarySearch_upper_floor(arr, target) {
      let l = -1
      let r = arr.length - 1
      while(l < r) {
        let mid = Math.floor(l + (r - l) / 2) + 1
        if(arr[mid] < target) {
          l = mid
        } else {
          r = mid - 1
        }
      }
    
      // console.log(l) // 3 3
    
      if(arr[l + 1] !== target) {
        return l
      } else {
        while(arr[l+1] === target) {
          l++
        }
        return l
      }
    }
    
    let array = [1,1,3,3,5,5]
    console.log(binarySearch_upper_floor(array, 5)) // 5
    console.log(binarySearch_upper_floor(array, 4)) // 3
    console.log(binarySearch_upper_floor(array, 6)) // 5
    
    let array1 = [1,3,5,7,9]
    console.log(binarySearch_upper_floor(array1, 3)); // 1
    console.log(binarySearch_upper_floor(array1, 4)); // 1
    console.log(binarySearch_upper_floor(array1, 0)); // -1
    console.log(binarySearch_upper_floor(array1, 10)); // 4
    
    
这篇关于二分搜索各种情况总结的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!