备案控制台
探索云世界
开发者社区 开发与运维 文章 正文

一个几乎全民都会的算法——二分查找

2023-05-28 52
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 一个几乎全民都会的算法——二分查找

为什么说二分查找是全民都会的算法？



佳宾报价：主持人说高或低

1800：高了

1500：低了

1600：低了

1700：高了

1680：高了

1660：低了

1670：正确！

上面这个猜价格过程，首先佳宾预估到这件的商品价格区间是1500到1800之间，然后根据主持人说高还是低进行调节报价高低，直到猜中价格。


是不是很简单！ 其实这一个猜价格过程就是二分查找算法。由于2000年前后的手机还没有多媒体化，这档节目收视率极高，所以这种猜价格的方法那时候几乎全民皆会，只是没命名它叫二分查找而已。





二分查找

也被称为折半查找，它的基本思想是：对于一个有序数组，每次查找中间位置的元素，如果该元素等于目标元素，则返回该元素的位置；如果该元素大于目标元素，则在数组的左半部分继续查找；如果该元素小于目标元素，则在数组的右半部分继续查找。重复以上过程，直到找到目标元素或者数组中不存在目标元素为止。


二分查找时间复杂度为O(log n)，是一种非常高效的查找算法。


基本过程


1.首先，将数组按照升序或者降序排列。

2.然后，确定数组的中间元素。

3.接着，将目标值与中间元素进行比较。

　3-1.如果目标值等于中间元素，则查找成功，返回中间元素的位置。

　3-2.如果目标值小于中间元素，则在左侧子数组中继续查找。

　3-3.如果目标值大于中间元素，则在右侧子数组中继续查找。

重复执行步骤，直到查找成功或者确定目标元素不存在。



算法实现

给定一个有序数组和一个目标元素，求该元素在数组中的位置，如果数组中不存在该元素，则返回-1。例如，给定数组[1, 2, 3, 6, 8, 9, 10]和目标元素8，则返回3。

用Golang语言实现的代码如下：

package main
import "fmt"
// 二分查找算法
func binarySearch(nums []int, target int) int {
  left, right := 0, len(nums)-1
  for left <= right {
    mid := (left + right) / 2
    if nums[mid] == target {
      return mid
    } else if nums[mid] > target {
      right = mid - 1
    } else {
      left = mid + 1
    }
  }
  return -1
}
func main() {
  nums := []int{1, 2, 3, 6, 8, 9, 10}
  target := 8
  fmt.Println(binarySearch(nums, target))
}

运行结果： 4，表示数组的第5个元素是8.


在本例中，我们定义了一个名为binarySearch的函数，该函数接受两个参数：


nums：有序数组， target：目标元素


在函数中，首先定义两个指针left和right，分别指向数组的左边界和右边界。然后使用一个循环，不断查找中间位置的元素，直到找到目标元素或者数组中不存在目标元素为止。在每次循环中，首先计算中间位置的索引mid，如果中间位置的元素等于目标元素，则返回中间位置的索引；如果中间位置的元素大于目标元素，则在数组的左半部分继续查找，将右边界指向中间位置的左侧；如果中间位置的元素小于目标元素，则在数组的右半部分继续查找，将左边界指向中间位置的右侧。重复以上过程，直到找到目标元素或者数组中不存在目标元素为止。


二分查找算法虽然简单，但是实现起来需要注意几个问题：


如何计算中间位置：在二分查找算法中，需要计算中间位置的索引，通常可以使用left和right指针来计算，即mid := (left + right) / 2，也有用右移运算的：(left + right) >> 1。


特别是当right接近最大整数Int_Max时，避免left,right相加后溢出，尽可能用：


mid := left + (right - left) / 2 或者 mid := left + (right - left) >> 1



递归法

递归法更好地展示了二分查找的过程：


package main
import "fmt"
// 二分查找算法
func binarySearchRecursive(arr []int, target int, left int, right int) int {
  if left > right {
    return -1
  }
  mid := left + (right-left)/2
  if arr[mid] == target {  //“正确”
    return mid
  } else if target < arr[mid]  {  //“高了”
    return binarySearchRecursive(arr, target, left, mid-1)
  } else {  //“低了”
    return binarySearchRecursive(arr, target, mid+1, right)
  }
}
func main() {
  nums := []int{1, 2, 3, 6, 8, 9, 10}
  target := 8
  left, right := 0, len(nums)-1
  fmt.Println(binarySearchRecursive(nums, target, left, right))
}




例程演示

用代码实现前文提到的猜价格游戏：

package main
import "fmt"
// 二分查找算法
func binarySearchRecursive(target int, low int, high int, count int) int {
  if low > high {
    return -1
  }
  count++
  mid := low + (high-low)/2
  fmt.Printf("第%v次报价:%v ", count, mid)
  if mid == target {
    fmt.Println("正确！")
    return mid
  } else if target < mid {
    fmt.Println("高了")
    return binarySearchRecursive(target, low, mid-1, count)
  } else {
    fmt.Println("低了")
    return binarySearchRecursive(target, mid+1, high, count)
  }
}
func main() {
  target := 1670          //商品正确价格为1670元
  low, high := 1500, 1800 //预估商品价格区间
  binarySearchRecursive(target, low, high, 0)
}


运行结果：  

第1次报价:1650 低了

第2次报价:1725 高了

第3次报价:1687 高了

第4次报价:1668 低了

第5次报价:1677 高了

第6次报价:1672 高了

第7次报价:1670 正确！


加上预估区间的2次，共9次猜出正确价格。为什么比人猜多了，因为人猜时默认价格是10的倍数，是没有个位数的。修改代码，也用mid+10 和 mid-10试试：


package main
import "fmt"
// 二分查找算法
func binarySearchRecursive(target int, low int, high int, count int) int {
  if low > high {
    return -1
  }
  count++
  mid := low + (high-low)/2
  fmt.Printf("第%v次报价:%v ", count, mid)
  if mid == target {
    fmt.Println("正确！")
    return mid
  } else if target < mid {
    fmt.Println("高了")
    return binarySearchRecursive(target, low, mid-10, count)
  } else {
    fmt.Println("低了")
    return binarySearchRecursive(target, mid+10, high, count)
  }
}
func main() {
  target := 1670          //商品正确价格为1670元
  low, high := 1500, 1800 //预估商品价格区间
  binarySearchRecursive(target, low, high, 0)
}


运行结果：  

第1次报价:1650 低了

第2次报价:1730 高了

第3次报价:1690 高了

第4次报价:1670 正确！


虽然这个例子是猜中了，但对区间变动不是mid±1的还是谨慎使用，很可能会错失目标的。

盲猜：

如果不知道是什么商品，也就是估不准价格，比如我们指定是100000以内价格区间，看要猜多少次？


package main
import "fmt"
// 二分查找算法
func binarySearchRecursive(target int, low int, high int, count int) int {
  if low > high {
    return -1
  }
  count++
  mid := low + (high-low)/2
  fmt.Printf("第%v次报价:%v ", count, mid)
  if mid == target {
    fmt.Println("正确！")
    return mid
  } else if target < mid {
    fmt.Println("高了")
    return binarySearchRecursive(target, low, mid-1, count)
  } else {
    fmt.Println("低了")
    return binarySearchRecursive(target, mid+1, high, count)
  }
}
func main() {
  target := 1670         //商品正确价格为1670元
  low, high := 0, 100000 //预估商品价格区间
  binarySearchRecursive(target, low, high, 0)
}



运行结果：  

第1次报价:50000 高了

第2次报价:24999 高了

第3次报价:12499 高了

第4次报价:6249 高了

第5次报价:3124 高了

第6次报价:1561 低了

第7次报价:2342 高了

第8次报价:1951 高了

第9次报价:1756 高了

第10次报价:1658 低了

第11次报价:1707 高了

第12次报价:1682 高了

第13次报价:1670 正确！

这个次数不高于log2(100000) ≈ 16.61，所以二分查找的时间复杂度为 O(log n)。



力扣实战


查找元素的首末位置


Find-first-and-last-position-of-element-in-sorted-array


给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。


如果数组中不存在目标值 target，返回 [-1, -1]。

进阶：

   你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗？


示例 1：

输入：nums = [5,7,7,8,8,10], target = 8

输出：[3,4]


示例 2：

输入：nums = [5,7,7,8,8,10], target = 6

输出：[-1,-1]


示例 3：

输入：nums = [], target = 0

输出：[-1,-1]


提示：

   0 <= nums.length <= 10^5

   -10^9 <= nums[i] <= 10^9

   nums 是一个非递减数组

   -10^9 <= target <= 10^9

代码：  

package main
import "fmt"
func searchRange(nums []int, target int) []int {
  left, right := -1, -1
  // 查找左边界
  l, r := 0, len(nums)-1
  for l <= r {
    mid := (l + r) / 2
    if nums[mid] == target {
      left = mid
      r = mid - 1
    } else if nums[mid] > target {
      r = mid - 1
    } else {
      l = mid + 1
    }
  }
  // 如果左边界没找到，直接返回
  if left == -1 {
    return []int{-1, -1}
  }
  // 查找右边界
  l, r = 0, len(nums)-1
  for l <= r {
    mid := (l + r) / 2
    if nums[mid] == target {
      right = mid
      l = mid + 1
    } else if nums[mid] > target {
      r = mid - 1
    } else {
      l = mid + 1
    }
  }
  return []int{left, right}
}
func main() {
  nums := []int{5, 7, 7, 8, 8, 10}
  fmt.Println(searchRange(nums, 8))
  fmt.Println(searchRange(nums, 6))
  nums = []int{}
  fmt.Println(searchRange(nums, 0))
}



x 的平方根  Sqrt x


给你一个非负整数 x ，计算并返回 x 的 算术平方根 。

由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。

注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。


示例 1：


输入：x = 4

输出：2


示例 2：

输入：x = 8

输出：2

解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。


提示：

  • 0 <= x <= 2^31 - 1

代码： 

package main
import (
  "fmt"
)
func mySqrt(x int) int {
  left, right := 0, x
  res := -1
  for left <= right {
    mid := left + (right-left)/2
    guess := mid * mid
    if guess <= x {
      res = mid
      left = mid + 1
    } else {
      right = mid - 1
    }
  }
  return res
}
func main() {
  fmt.Println(mySqrt(4))
  fmt.Println(mySqrt(8))
  fmt.Println(mySqrt(122))
}


寻找旋转排序数组中的最小值


Find-minimum-in-rotated-sorted-array


已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：


   若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]

   若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]


注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。

给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。


你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。


示例 1：

输入：nums = [3,4,5,1,2]

输出：1

解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。


示例 2：

输入：nums = [4,5,6,7,0,1,2]

输出：0

解释：原数组为 [0,1,2,4,5,6,7] ，旋转 4 次得到输入数组。


示例 3：

输入：nums = [11,13,15,17]

输出：11

解释：原数组为 [11,13,15,17] ，旋转 4 次得到输入数组。


提示：

   n == nums.length

   1 <= n <= 5000

   -5000 <= nums[i] <= 5000

   nums 中的所有整数 互不相同

   nums 原来是一个升序排序的数组，并进行了 1 至 n 次旋转


代码：  

package main
import "fmt"
func findMin(nums []int) int {
  left, right := 0, len(nums)-1
  for left < right {
    mid := left + (right-left)/2
    if nums[mid] > nums[right] {
      left = mid + 1
    } else {
      right = mid
    }
  }
  return nums[left]
}
func main() {
  nums := []int{3, 4, 5, 1, 2}
  fmt.Println(findMin(nums))
  nums = []int{4, 5, 6, 7, 0, 1, 2}
  fmt.Println(findMin(nums))
  nums = []int{11, 13, 15, 17}
  fmt.Println(findMin(nums))
}




寻找峰值


Find Peak Element


峰值元素是指其值严格大于左右相邻值的元素。

给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。

你可以假设 nums[-1] = nums[n] = -∞ 。

你必须实现时间复杂度为 O(log n) 的算法来解决此问题。


示例 1：

输入：nums = [1,2,3,1]

输出：2

解释：3 是峰值元素，你的函数应该返回其索引 2。


示例 2：

输入：nums = [1,2,1,3,5,6,4]

输出：1 或 5  

解释：你的函数可以返回索引 1，其峰值元素为 2；

    或者返回索引 5， 其峰值元素为 6。


提示：

   1 <= nums.length <= 1000

   -2^31 <= nums[i] <= 2^31 - 1

   对于所有有效的 i 都有 nums[i] != nums[i + 1]

代码：  

package main
import "fmt"
func findPeakElement(nums []int) int {
  left, right := 0, len(nums)-1
  for left < right {
    mid := left + (right-left)/2
    if nums[mid] > nums[mid+1] {
      right = mid
    } else {
      left = mid + 1
    }
  }
  return left
}
func main() {
  nums := []int{1, 2, 3, 1}
  fmt.Println(findPeakElement(nums))
  nums = []int{1, 2, 1, 3, 5, 6, 4}
  fmt.Println(findPeakElement(nums))
}


有效的完全平方数


Valid Perfect Square

给定一个 正整数num ，编写一个函数，如果 num 是一个完全平方数，则返回 true ，否则返回 false 。

进阶：不要 使用任何内置的库函数，如  sqrt 。


示例 1：

输入：num = 16

输出：true


示例 2：

输入：num = 14

输出：false


提示：

  • 1 <= num <= 2^31 - 1

代码：

package main
import "fmt"
func isPerfectSquare(num int) bool {
  left, right := 1, num
  for left <= right {
    mid := left + (right - left) / 2
    square := mid * mid
    if square == num {
      return true
    } else if square < num {
      left = mid + 1
    } else {
      right = mid - 1
    }
  }
  return false
}
func main() {
  fmt.Println(isPerfectSquare(16))
  fmt.Println(isPerfectSquare(14))
}



分割数组的最大值

Split-array-largest-sum


给定一个非负整数数组 nums 和一个整数 m ，你需要将这个数组分成 m 个非空的连续子数组。

设计一个算法使得这 m 个子数组各自和的最大值最小。


示例 1：

输入：nums = [7,2,5,10,8], m = 2

输出：18


解释：

一共有四种方法将 nums 分割为 2 个子数组。  

其中最好的方式是将其分为 [7,2,5] 和 [10,8] 。

因为此时这两个子数组各自的和的最大值为18，在所有情况中最小。


示例 2：

输入：nums = [1,2,3,4,5], m = 2

输出：9


示例 3：

输入：nums = [1,4,4], m = 3

输出：4

提示：

   1 <= nums.length <= 1000

   0 <= nums[i] <= 10^6

   1 <= m <= min(50, nums.length)

package main
import "fmt"
func splitArray(nums []int, m int) int {
  left, right := 0, 0
  for _, num := range nums {
    right += num
    if left < num {
      left = num
    }
  }
  for left <= right {
    mid := left + (right-left)/2
    if check(nums, m, mid) {
      right = mid - 1
    } else {
      left = mid + 1
    }
  }
  return left
}
func check(nums []int, m, target int) bool {
  sum, cnt := 0, 1
  for _, num := range nums {
    if sum+num <= target {
      sum += num
    } else {
      sum = num
      cnt++
      if cnt > m {
        return false
      }
    }
  }
  return true
}
func main() {
  nums := []int{7, 2, 5, 10, 8}
  fmt.Println(splitArray(nums, 2))
  nums = []int{1, 2, 3, 4, 5}
  fmt.Println(splitArray(nums, 2))
  nums = []int{1, 4, 4}
  fmt.Println(splitArray(nums, 3))
}



第 k 个缺失的正整数

kth-missing-positive-number

给你一个 严格升序排列 的正整数数组 arr 和一个整数 k 。


请你找到这个数组里第 k 个缺失的正整数。


示例 1：

输入：arr = [2,3,4,7,11], k = 5

输出：9

解释：缺失的正整数包括 [1,5,6,8,9,10,12,13,...] 。第 5 个缺失的正整数为 9 。


示例 2：

输入：arr = [1,2,3,4], k = 2

输出：6

解释：缺失的正整数包括 [5,6,7,...] 。第 2 个缺失的正整数为 6 。


提示：

   1 <= arr.length <= 1000

   1 <= arr[i] <= 1000

   1 <= k <= 1000

   对于所有 1 <= i < j <= arr.length 的 i 和 j 满足 arr[i] < arr[j]  


代码：

package main
import "fmt"
func findKthPositive(arr []int, k int) int {
  left, right := 0, len(arr)
  for left < right {
    mid := left + (right-left)/2
    // 计算当前位置缺失的数字个数
    count := arr[mid] - mid - 1
    // 如果缺失的数字个数小于k，说明第k个缺失的数字在右半部分
    if count < k {
      left = mid + 1
    } else {
      right = mid
    }
  }
  // 缺失的数字个数为k时，需要返回arr[left]-1
  // 因为arr[left]之前的数字都不缺失，所以缺失的第k个数字就是arr[left]+k
  return left + k
}
func main() {
  nums := []int{2, 3, 4, 7, 11}
  fmt.Println(findKthPositive(nums, 5))
  nums = []int{1, 2, 3, 4}
  fmt.Println(findKthPositive(nums, 2))
}


还有很多适用十分查找的题目，不一一列举了。



总结


本文介绍了二分查找算法的原理、实现方法和用 Golang 实现的例程。二分查找算法是一种高效的查找算法，适用于有序数列中的查找问题。它的时间复杂度为 O(log n)，相比于线性查找的 O(n)，效率更高。在实际应用中，我们可以根据具体情况选择递归或循环实现二分查找算法，以提高算法的效率。


最后，请记牢二分查找标志性的语句：


mid := left + (right-left)/2










文章标签：
Go
索引
算法
关键词：
算法二分查找
HannYang
目录
相关文章
起飞的风筝
|
1月前
|
存储 算法 索引
【优选算法】—— 二分查找
【优选算法】—— 二分查找
起飞的风筝
32 0
那一脸阳光
|
1月前
|
算法 程序员 数据处理
算法与人生 揭秘C语言中高效搜索的秘诀——二分查找算法详解
算法与人生 揭秘C语言中高效搜索的秘诀——二分查找算法详解
那一脸阳光
20 1
闻缺陷则喜何志丹
|
2月前
|
人工智能 算法 测试技术
【动态规划】【二分查找】C++算法 466 统计重复个数
【动态规划】【二分查找】C++算法 466 统计重复个数
闻缺陷则喜何志丹
26 1
闻缺陷则喜何志丹
|
3月前
|
算法 测试技术 C#
【KMP】【二分查找】【C++算法】100207. 找出数组中的美丽下标 II
【KMP】【二分查找】【C++算法】100207. 找出数组中的美丽下标 II
闻缺陷则喜何志丹
21 0
闻缺陷则喜何志丹
|
3月前
|
算法 测试技术 C#
C++二分查找算法：包含每个查询的最小区间
C++二分查找算法：包含每个查询的最小区间
闻缺陷则喜何志丹
37 0
东方睿赢
|
4月前
|
算法 JavaScript 前端开发
JavaScript算法和数据结构：写一个二分查找的函数。
JavaScript算法和数据结构：写一个二分查找的函数。
东方睿赢
32 0
不能再留遗憾了
|
3月前
|
存储 算法 Java
【算法系列篇】二分查找——这还是你所知道的二分查找算法吗？
【算法系列篇】二分查找——这还是你所知道的二分查找算法吗？
不能再留遗憾了
54 0
小陈在拼命
|
26天前
|
算法 索引
算法思想总结：二分查找算法
算法思想总结：二分查找算法
小陈在拼命
19 1
xxxhuxxx
|
2月前
|
机器学习/深度学习 算法 Java
【数据结构查找算法篇】----二分查找【实战项目】
【数据结构查找算法篇】----二分查找【实战项目】
xxxhuxxx
24 1
闻缺陷则喜何志丹
|
2月前
|
算法 测试技术 C++
【KMP】【二分查找】【C++算法】100207. 找出数组中的美丽下标 II
【KMP】【二分查找】【C++算法】100207. 找出数组中的美丽下标 II
闻缺陷则喜何志丹
28 0

热门文章

最新文章

  • 1
    【MATLAB】GA_ELM神经网络时序预测算法
  • 2
    RPN(Region Proposal Networks)候选区域网络算法解析（附PyTorch代码）
  • 3
    使用Python实现DBSCAN聚类算法
  • 4
    【软件设计师备考 专题 】算法探索：排序、查找、数值计算和字符串处理（一）
  • 5
    【C++ 数据结构与算法 一站式备考指南】一文掌握 数据结构与算法课程 知识点（二）
  • 6
    Docker Swarm总结+service创建和部署、overlay网络以及Raft算法（2/5）
  • 7
    C++ Algorithm 库 算法秘境探索（Algorithm Wonderland Exploration）
  • 8
    R语言聚类算法的应用实例
  • 9
    经典控制算法——PID算法原理分析及优化
  • 10
    [YOLOv8/YOLOv7/YOLOv5系列算法改进NO.5]改进特征融合网络PANET为BIFPN（更新添加小目标检测层yaml）
  • 1
    MVVM模型，虚拟DOM和diff算法
    124
  • 2
    Opencv（C++）学习系列---Laplacian拉普拉斯边缘检测算法
    20
  • 3
    Opencv(C++)学习系列---Canny边缘检测算法
    21
  • 4
    使用python实现FP-Growth算法
    24
  • 5
    使用C语言实现DES算法代码
    26
  • 6
    关于Dijkstra算法
    11
  • 7
    ICLR 2024：近似最优的最大损失函数量子优化算法
    26
  • 8
    基于yolov2深度学习网络的视频手部检测算法matlab仿真
    23
  • 9
    Python基础算法解析：支持向量机（SVM）
    35
  • 10
    探索数据结构在算法优化中的关键作用
    34

    • 相关课程

    更多
  • 相册服务中的故事生成算法介绍
  • Go语言核心编程 - 数据结构和算法
  • 神经网络概览及算法详解

    • 相关电子书

    更多
  • 数据+算法定义新世界
  • 袋鼠云基于实时计算的反黄牛算法
  • Alink：基于Apache Flink的算法平台

    • 相关实验场景

    更多
  • TLS1.3的后量子算法集成
  • RSA非对称加密算法
    • 下一篇
    阿里云oss简介和使用流程