算法系列之二分查找法

概述

二分查找是一种算法，其输入是一个有序的元素列表。如果要查找的元素包含列表中，二分查找返回其位置; 否则返回null

---

举例

这些列子其实都属于查找问题，都可以用二分查找法解决。而且列子中你的想法就和二分法有了很大了关联

• 假设要在电话簿中找一个名字以K打头的人，你可以从电话簿开始的位置翻页，直到进入以K打头的那部分。但你很可能不这样做，而是先跳到电话簿中间的位置，从中间开始翻页，因为你知道以K打头的名字在电话簿中间的位置
• 假设要在字典中找一个以 O 开头的单词，你也不会从头翻，而且直接从字典的中后位置查找

---

图文理解

• 我随便想一个1～100的数字

  
  

• 你的目标是以最少的次数猜到这个数字。你每次猜测后，我会说小了、大了或对了。
  假设你从1开始依次往上猜，猜测过程会是这样

  
  
• 这是一种糟糕的猜数法，属于简单查找。每次猜测都只能排除一个数字。如果我想的数字是99，你得猜99次才能猜到！
• 看一下接下来这种更佳的猜法

• 从50开始猜

  
  

• 小了，但排除了一半的数字！至此，你知道1～50都小了。接下来，你猜75

  
  

• 大了，那余下的数字又排除了一半！使用二分查找时，你猜测的是中间的数字，从而每次都将余下的数字排除一半。接下来，你猜63（50和75中间的数字）

  
  

• 这就是二分查找算法！每次猜测排除的数字个数如下。

  
  
• 最多七步就搞定了，使用二分查找时，每次都排除一半的数字。不管我心里想的是哪个数字，你在7次之内都能猜到，因为每次猜测都将排除很多数字
• 假设你要在字典中查找一个单词，而该字典包含240 000个单词，你认为每种查找最多需要多少步？

• 如果要查找的单词位于字典末尾，使用简单查找将需要240 000步。使用二分查找时，每次排除一半单词，直到最后只剩下一个单词

  
  
• 因此，使用二分查找只需18步——少多了！一般而言，对于包含n个元素的列表，用二分查找最多需要log₂n步，而简单查找最多需要n步。
• log₂n 是对数，还记得么，没关系，这篇简书后面的部分会帮助你简单复习一下相关数学知识

代码理解二分查找法

• 定义一个List itemList 有序列表。定义 currentItem 为猜想的数字

int low = 0;
int high = itemList.Count - 1;

• 你每次都应该检查中间的元素

int mid = (low + high) / 2; //如果(low + high)不是偶数，将mid向下圆整。

• 如果猜的数字小了，就相应地修改low

if (itemList[mid] < currentItem)
{
     low = mid + 1;
}

• 如果猜的数字大了，就修改high

if (itemList[mid] > currentItem)
{
     high = mid - 1;
}

完整的代码如下

• 使用递归的方式

using System.Collections.Generic;
using UnityEngine;
/// <summary>
/// 转载请注明唯一出处 - 简书
/// 简书地址：https://www.jianshu.com/u/ab8f5ab027bd
/// 简书作者：SunnyShao
/// 创作时间：2021年9月13号
/// </summary>
public class BinarySearchTest : MonoBehaviour
{
    public int currentItem = default(int);          //目标值
    public List<int> itemList = new List<int>();    //目标集合

    private void Awake()
    {
        Debug.Log($"找到的索引 = {BinarySearch_Recursion(0, itemList.Count - 1)}");
    }

    //使用递归的方法进行 二分查找法
    private int BinarySearch_Recursion(int low, int high)
    {
        int mid = (low + high) / 2;

        if (low > high)
        {
            return -1;
        }
        else
        {
            if (itemList[mid] == currentItem)
            {
                return mid;
            }
            else if (itemList[mid] < currentItem)
            {
                low = mid + 1;
                return BinarySearch_Recursion(low, high);
            }
            else
            {
                high = mid - 1;
                return BinarySearch_Recursion(low, high);
            }
        }
    }
}

• 使用while循环的方式

    //使用循环的方式进行 二分查找法
    private int BinarySearch_While()
    {
        int low = 0;
        int high = itemList.Count - 1;
        int mid;
        while (low <= high)                         //只要范围没有缩小到只包含一个元素
        {
            mid = (low + high) / 2;                 //就检查中间的元素
            if (itemList[mid] == currentItem)
            {
                return mid;
            }
            else if (itemList[mid] < currentItem)
            {
                low = mid + 1;
            }
            else if (itemList[mid] > currentItem)
            {
                high = mid - 1;
            }
        }
        return -1;
    }

---

大O表示法

大O表示法指出了算法有多快。例如，假设列表包含n个元素。简单查找需要检查每个元素，因此需要执行n次操作。使用大O表示法，这个运行时间为O(n)。大O表示法指的并非以秒为单位的速度。大O表示法让你能够比较操作数，它指出了算法运行时间的增速。

• 一些常见的大 O 运行时间
  O(log n)，也叫对数时间，这样的算法包括二分查找。
  O(n)，也叫线性时间，这样的算法包括简单查找。
  O(n * log n)，这样的算法包括快速排序等——一种速度较快的排序算法。
  O(n2)，这样的算法包括选择排序——一种速度较慢的排序算法。
  O(n!)，这样的算法包括著名旅行商问题的解决方案——一种非常慢的算法。

二分查找法运行时间

检查长度为n的列表，二分查找需要执行log n次操作。使用大O表示法，这个运行时间怎么表示呢？O(log n)

对数复习

参考

《算法图解》（确实像小说一样有趣的算法书）