Skip to content

二分查找

二分查找

思考

顺序查找固然简单，也好理解，但是明显效率非常低，有没有更好的可以提高效率的方式呢？

什么是二分查找

uml diagram

  • 二分查找是一种在有序数组中查找元素的算法。
  • 将数组分成两部分，判断目标元素可能在哪一部分。
  • 直到找到目标元素或确定目标元素不存在于数组中。

二分查找与顺序查找的对比

顺序查找 二分查找
查找次数 8 3
查找次数 n log2(n)

二分查找的实现思路

  1. 确定查找范围。
  2. 获取中间元素。
  3. 如果猜的数字小了，就修改最小值。
  4. 如果猜的数字大了，就修改最大值。
  5. 如果猜中了，则返回下标。
  6. 重复以上的过程直到找到目标元素或确定目标元素不存在于数组中。

uml diagram

上图是要查找的列表，查找目标是7，此时在第一轮查找的过程中，最小值为数组的第一位元素的索引，也就是0。最大值为数组最后一位元素的索引，也就是7。中间值等于（最小值+最大值）/2，也就是3（向下整除）。

uml diagram

使用Python 实现为：

low  = 0
# 最大数据的索引
high = len(nums)-1
mid = (low + high) // 2

如果猜中了，则返回索引，如果猜的数字小了，就修改最小值。如果猜的数字大了，就修改最大值。

此时目标元素为7，大于中间值，代表中间元素以及其左边的数据全都不可能匹配到目标元素，所以最小值就缩小到中间元素的下一位。最小值索引变为4（对应值为5），中间元素的索引变为5（对应值为6）。

uml diagram

使用 Python 实现其完整逻辑为：

# 如果猜中了
if guess == target:
    return mid
# 猜的值大于中间值，最小值变为中间值+1
elif guess < target:
    low = mid + 1
# 猜的值小于中间值，最大值变为中间值-1
else:
    high = mid - 1

因为无法保证一轮就能够猜中目标元素，所以需要重复以上的过程直到找到目标元素或确定目标元素不存在于数组中。因为重复的过程就是在不停的缩小最小或最大边界的过程，所以只要最大值>=最小值，即可一直循环进行查找操作。

uml diagram

uml diagram

uml diagram

又由上图的过程可知，在整个循环过程中，最大值、最小值、中间值，这三个数据一直都会随着循环变化。所以对应的代码实现应该为：

while low <= high:
    # 中间值随着循环的变化
    mid = (low + high) // 2
    guess = nums[mid]
    # 如果猜中了
    if guess == target:
        return mid
    # 猜的数字小了。
    elif guess < target:
        low = mid + 1
    # 猜的数字大了。
    else:
        high = mid - 1

完整代码（Python）

完整版的代码为：

def binary_search(nums, target: int) -> int:
    """
    在有序数组arr中查找目标元素target
    返回目标元素的索引，如果目标元素不存在，则返回-1
    """
    # low 和 high 用于跟踪要在其中查找的列表的部分
    low  = 0
    high = len(nums)-1
    while low <= high:
        mid = (low + high) // 2
        guess = nums[mid]
        if guess == target:
            return mid
        # 猜的数字小了。
        elif guess < target:
            low = mid + 1
        # 猜的数字大了。
        else:
            high = mid - 1
    # 没有指定的元素。
    return -1

使用测试用例测试算法是否实现。在测试过程中，应当充分考虑异常与边界值的场景：

def test_binary_search():
    # 异常场景
    assert binary_search([1, 3, 4, 5, 7, 8], 11) == -1
    # 找最小值
    assert binary_search([1, 3, 4, 5, 7, 8], 1) == 0
    # 找最大值
    assert binary_search([1, 3, 4, 5, 7, 8], 8) == 5

完整代码（Java）

// 二分查找的实现
public class BinarySearch {
    public int binarySearch(int[] nums, int target){
        int low = 0;
        int high = nums.length - 1;
        while (low<=high){
            int mid = (low+high)/2;
            if (nums[mid] == target){
                return mid;
            } else if (nums[mid]>target) {
                high = mid - 1;
            }else {
                low = mid + 1;
            }
        }
    return  -1;
    }
}

// 测试用例
import org.junit.jupiter.api.Test;

import static org.junit.jupiter.api.Assertions.*;

class BinarySearchTest {

    @Test
    void binarySearch() {

        BinarySearch bb = new BinarySearch();

        int[] arr = {11, 22, 33, 44, 55, 66, 77};
        assert bb.binarySearch(arr, 33) == 2;
        // 不存在的场景
        assert bb.binarySearch(arr, 99) == -1;
        // 边界值
        assert bb.binarySearch(arr, 11) == 0;
        assert bb.binarySearch(arr, 77) == 6;
    }
}

相关题目