数据结构与算法基础篇--二分查找

必要前提:有序数组

算法简述:通过不断取中间值和目标target值进行比较(中间值:mid = (left + right) / 2)

  • 如果目标值等于中间位置的值,则找到目标,返回中间位置
  • 如果目标值小于中间位置的值,则在左半部分继续查找:更新右边界为 right = mid - 1
  • 如果目标值大于中间位置的值,则在右半部分继续查找:更新左边界为 left = mid + 1

二分查找的时间复杂度: O(log n),其中 n 是要查找的元素个数(通常是一个有序数组的长度)。

java代码实现

    // 二分查找方法
    public static int binarySearch(int[] array, int target) {
        int left = 0;
        int right = array.length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (array[mid] == target) {
                return mid; // 找到目标值,返回索引
            } else if (array[mid] < target) {
                left = mid + 1; // 目标值在右半部分
            } else {
                right = mid - 1; // 目标值在左半部分
            }
        }

        return -1; // 没有找到目标值
    }

这里解释一下为什么中间值用这种int mid = left + (right - left) / 2写法,

而不是这种int mid = (right + left) / 2;

1,避免溢出风险

在 Java 中,int类型的最大值是 2^31 - 1,如果 leftright 非常大,直接计算 mid = (left + right) / 2; 可能会导致溢出。

2,清晰明了

使用 left + (right - left) / 2 明确地展示了计算 mid 的逻辑,使得代码更加清晰易懂。直观地表达了将 leftright 之间的中点作为 mid 的计算方法。

github中二分法图像化展示

二分法html,欢迎各位直接拉到本地展示使用

力扣中关于二分法的题目编号

  • 简单难度

        704,35,278,374,69

  • 中等难度

        33,34,240,162,300

  • 困难难度

        4,154,287,875,668

相关推荐

  1. 数据结构算法基础--二分查找

    2024-07-11 02:26:03       8 阅读
  2. 算法基础二分查找

    2024-07-11 02:26:03       21 阅读
  3. 数据结构-二分查找

    2024-07-11 02:26:03       27 阅读
  4. 数据结构算法 | 基础】环形数组模拟队列

    2024-07-11 02:26:03       18 阅读
  5. 数据结构算法 | 基础数组模拟栈

    2024-07-11 02:26:03       16 阅读

最近更新

  1. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-07-11 02:26:03       3 阅读
  2. Could not load dynamic library ‘cudart64_100.dll‘

    2024-07-11 02:26:03       3 阅读
  3. 在Django里面运行非项目文件

    2024-07-11 02:26:03       2 阅读
  4. Python语言-面向对象

    2024-07-11 02:26:03       2 阅读

热门阅读

  1. Redis原理-数据结构

    2024-07-11 02:26:03       10 阅读
  2. ArduPilot开源代码之AP_OpticalFlow_CXOF

    2024-07-11 02:26:03       10 阅读
  3. QT实现WebSocket通信

    2024-07-11 02:26:03       8 阅读
  4. Text2SQL提问中包括时间的实战方案

    2024-07-11 02:26:03       10 阅读
  5. 进程与线程的区别

    2024-07-11 02:26:03       10 阅读
  6. HTTP有哪些请求方式?

    2024-07-11 02:26:03       9 阅读
  7. 笔记

    2024-07-11 02:26:03       9 阅读
  8. 代码随想录Day76(图论Part11)

    2024-07-11 02:26:03       7 阅读
  9. 优雅下线的艺术:Eureka服务管理深度解析

    2024-07-11 02:26:03       9 阅读
  10. 【LeetCode】12. 小张刷题计划

    2024-07-11 02:26:03       8 阅读
  11. samout 最新版本state 逐层控制加速收敛

    2024-07-11 02:26:03       7 阅读