01-什么是二分查找

AI悦创原创2023年2月7日大约 6 分钟...约 1750 字

你好，我是悦创。

二分查找（Binary Search），是一种效率较高的查找方法。在面试或算法竞赛中，查找相关的问题最优解通常就是二分查找。特别在现场面试中尤其重要，常用二分查找来考察面试者的编码能力和算法思维。

二分查找也称为折半查找。如果一个查找问题能够用一个条件消除一半的查找区域，那么就对目标在特定空间搜索，从而减少查找空间。

边界处理!

虽然二分查找思路比较直观，但大部分面试者通常在边界处理的时候考虑不全，从而出错。

有很多原因导致二分查找处理边界失败！例如，当目标位于数组第0个索引时，或位于第 (n - 1) 个索引时，程序进入死循环。

所以课程的目标，就是通过对二分查找算法进行深入分析，总结出一套二分查找的算法模板，避免这些边界情况处理失败！

现在，跟随我们开始研究吧。

提示

二分查找的一个基本前提是列表必须是已排序的。这是因为二分查找的核心原理是基于已排序列表中间值的比较来确定下一步搜索的方向（左半部分或右半部分）。

1. 通用实现方式

1.1 算法模板

下面的代码是二分查找的一种标准实现方式：

left = 0
right = size of array       # 数组的大小

while (left + 1 < right)
    mid = (left + right) / 2          # 中间 mid 下标

    if (array[mid] == target)         # 检查已找到
        return mid
    else if (array[mid] < target)
        continue search in right side   # 在 右边区间搜索
    else
        continue search in left side    # 在 左边区间搜索

if (array[left] == target)          # 循环退出后进行判断
    return left

return -1

逐一分析下上面伪代码：

第1行：0 作为左边 left 索引。
第2行：数组大小作为右边 right 索引。因此，当访问 right 索引，需要小心越界。
第4行：当 left 和 right 之间没有元素时，while 循环结束。因此，注意如果数组中仅有一个元素，将跳过这个循环，此时需要14行代码进行处理。
第14行: 在循环外检查 left 索引上的元素，因为循环退出时，它可能是需要查找的数字 target。

2. 编码实现

下面是完整的二分查找代码：

C++

#include <iostream>
#include <vector>

using namespace std;

int searchInsert(vector<int> &nums, int target) {
    // 左索引的初始值为 0
    int left = 0;
    // 右索引的初始值是数组中元素的数量
    int right = nums.size();
    // left + 1 >= right 将完成 while 循环
    while (left + 1 < right) {
        int mid = (right + left) / 2;

        if (nums[mid] == target) {
            // mid是目标索引
            return mid;
        } else if (nums[mid] < target) {
            // 在数组的左半部分搜索是没有意义的
            left = mid;
        } else {
            // 在数组的右半部分搜索没有意义
            right = mid;
        }
    }
    // left 可以是目标的索引
    if (nums[left] == target) {
        return left;
    }
    // 目标不存在于数组中
    return -1;
}

int main() {
    vector<int> nums = {1, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59};

    cout << "Index of 37 is ---> " << searchInsert(nums, 37) << endl;
    cout << "Index of 1 is ---> " << searchInsert(nums, 1) << endl;
    cout << "Index of 59 is ---> " << searchInsert(nums, 59) << endl;
    cout << "Index of 25 is ---> " << searchInsert(nums, 25) << endl;

    return 0;
}

Java

class Solution {
    int binarySearch(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return -1;
        }

        // 左索引的初始值为 0
        int left = 0;
        // 右索引的初始值是数组中元素的数量
        int right = nums.length;
        // left + 1 >= right 将完成 while 循环
        while (left + 1 < right) {
            int mid = (right + left) / 2;

            if (nums[mid] == target) {
                // mid是目标索引
                return mid;
            } else if (nums[mid] < target) {
                // 在数组的左半部分搜索是没有意义的
                left = mid;
            } else {
                // 在数组的右半部分搜索没有意义
                right = mid;
            }
        }
        // left 可以是目标的索引
        if (nums[left] == target) {
            return left;
        }
        // 目标不存在于数组中
        return -1;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] nums = new int[]{1, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59};

        System.out.println("Index of 37 is ---> " + sol.binarySearch(nums, 37));
        System.out.println("Index of 1 is ---> " + sol.binarySearch(nums, 1));
        System.out.println("Index of 59 is ---> " + sol.binarySearch(nums, 59));
        System.out.println("Index of 25 is ---> " + sol.binarySearch(nums, 25));
    }
}

JavaScript

const binarySearch = function (nums, target) {
    if (!nums || nums.length === 0) {
        return -1;
    }

    // 左索引的初始值为 0
    let left = 0;
    // 右索引的初始值是数组中元素的数量
    let right = nums.length;
    // left + 1 >= right 将完成 while 循环
    while (left + 1 < right) {
        let mid = Math.floor((right + left) / 2);

        if (nums[mid] === target) {
            // mid是目标索引
            return mid;
        } else if (nums[mid] < target) {
            // 在数组的左半部分搜索是没有意义的
            left = mid;
        } else {
            // 在数组的右半部分搜索没有意义
            right = mid;
        }
    }
    // left 可以是目标的索引
    if (nums[left] === target) {
        return left;
    }
    // 目标不存在于数组中
    return -1;
}

const nums = [1, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59];

console.log(`Index of 37 is ---> ${binarySearch(nums, 37)}`);
console.log(`Index of 1 is ---> ${binarySearch(nums, 1)}`);
console.log(`Index of 59 is ---> ${binarySearch(nums, 59)}`);
console.log(`Index of 25 is ---> ${binarySearch(nums, 25)}`);

Python

def binarySearch(nums, target):
    if len(nums) == 0:
        return -1

    # 左索引的初始值为 0
    left = 0
    # 右索引的初始值是数组中元素的数量
    right = len(nums)
    # left + 1 >= right 时将完成while循环
    while left + 1 < right:
        mid = (right + left) // 2;

        if nums[mid] == target:
            # mid是目标的索引
            return mid
        elif nums[mid] < target:
            # 在数组的左半部分搜索没有意义
            left = mid
        else:
            # 在数组的右半部分搜索没有意义
            right = mid
    # left 可以是目标的索引
    if nums[left] == target:
        return left
    # 目标不存在于数组中
    return -1


def main():
    nums = [1, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59];

    print("Index of 37 is ---> " + str(binarySearch(nums, 37)))
    print("Index of 1 is ---> " + str(binarySearch(nums, 1)))
    print("Index of 59 is ---> " + str(binarySearch(nums, 59)))
    print("Index of 25 is ---> " + str(binarySearch(nums, 25)))


main()

下面是算法的可视化过程，以 37 为目标数字：

欢迎关注我公众号：AI悦创，有更多更好玩的等你发现！

公众号：AI悦创【二维码】

AI悦创·编程一对一

AI悦创·推出辅导班啦，包括「Python 语言辅导班、C++ 辅导班、java 辅导班、算法/数据结构辅导班、少儿编程、pygame 游戏开发」，全部都是一对一教学：一对一辅导 + 一对一答疑 + 布置作业 + 项目实践等。当然，还有线下线上摄影课程、Photoshop、Premiere 一对一教学、QQ、微信在线，随时响应！微信：Jiabcdefh

C++ 信息奥赛题解，长期更新！长期招收一对一中小学信息奥赛集训，莆田、厦门地区有机会线下上门，其他地区线上。微信：Jiabcdefh

方法一：QQ

方法二：微信：Jiabcdefh