二分查找

简介: 二分查找

二分查找的前提


网络异常,图片无法展示
|


使用递归实现二分查找


public static <E extends Comparable<E>> int search(E[] arr, E target) {
        return search(arr, 0, arr.length - 1, target);
    }
    private static <E extends Comparable<E>> int search(E[] arr, int l, int r, E target) {
        if(l > r) {
            return -1;
        }
        int mid = l + (r - l) / 2;
        if(arr[mid].compareTo(target) == 0) { // 刚好找到中间的位置
            return mid;
        }else if (arr[mid].compareTo(target) > 0) { // 查找mid前面的元素
            return search(arr, l, mid - 1, target);
        }else { //(arr[mid].compareTo(target) < 0)
            return search(arr, mid + 1, r, target);
        }
    }


使用非递归实现二分查找


private static <E extends Comparable<E>> int search1(E[] arr, E target) {
        int l = 0, r = arr.length - 1;
        while(l <= r) { // 数组中存在元素时
            int mid = l + ( r - l) / 2;
            if(arr[mid].compareTo(target) == 0) { // 刚好中间的元素就是
                return mid;
            }
            if(arr[mid].compareTo(target) > 0) { // 中间的元素小于target,接着查找右边的列表
                r = mid - 1;
            }else { // 中间的元素大于target, 接着查找左边的列表
                l = mid + 1;
            }
        }
        return -1;
    }


二分查找法的变种


查找大于target的最小值


  • 当未查找到这样的元素,那么将返回数组长度。


  • 当中间值大于等于目标值,那么查询返回下一边界需要加上上一次的中间值,所以r = mid。


网络异常,图片无法展示
|


/**
 * 查找大于target的最小值
 * @param arr
 * @param target
 */
public static <E extends Comparable<E>> int upper(E[] arr, E target) {
    int l = 0, r = arr.length;
    while(l < r) {
        int mid = l + (r - l) / 2;
        if(arr[mid].compareTo(target) == 0) {
            return mid + 1;
        }else if(arr[mid].compareTo(target) > 0) { // 这个r = mid是因为mid的位置可能是目标值
            r = mid;
        }else {
            l = mid + 1;
        }
    }
    // l和r最后都都指向同一个位置。没找到则返回arr.length
    return l;
}


查找目标元素最大的下标元素 ceil


  • 如果有等于target的元素就返回最大的下标元素。


  • 如果没有等于target的元素,那么就返回大于target的最小元素。即上面实现的upper函数。


网络异常,图片无法展示
|


public static <E extends Comparable<E>> int ceil(E[] arr, E target) {
        int index = upper(arr, target);
        if(arr[index - 1].compareTo(target) == 0) {
            return index - 1;
        }
        return index;
    }


查找目标元素最小的小标元素 lower_ceil


  • 如果有等于target的元素就返回最小的下标元素。


  • 如果没有等于target的元素,那么就返回大于target的最小元素。即上面实现的upper函数。


网络异常,图片无法展示
|


查找小于target的最大值


网络异常,图片无法展示
|


按照上面的逻辑写成的程序会出现死循环


网络异常,图片无法展示
|


网络异常,图片无法展示
|


LeetCode相关习题


LeetCode 875


网络异常,图片无法展示
|


/**
     * 使用二分法,解决leetCode875
     * @param piles
     * @return
     */
    public static int leetCode875(int[] piles, int h) {
        // 假设他先吃二分法中间的那个根数
        int l = 1; // 最少吃一根
        int r = Arrays.stream(piles).max().getAsInt(); // 假设吃数组中最大数量的根数
        while(l < r) {
            int mid = l + (r - l) / 2;
            if(eatingTime(piles, mid) <= h) { // 此时mid可能会目标值
                r = mid;
            }else {
                l = mid + 1;
            }
        }
        return l;
    }
    public static int eatingTime(int[] arr, int k) {
        int res = 0;
        for(int pile: arr) {
            res = res + pile / k + (pile % k > 0 ? 1 : 0);
        }
        return res;
    }


LeetCode 1011


网络异常,图片无法展示
|


相关文章
|
18天前
|
Linux 开发工具 iOS开发
Codex保姆级教程(下载+安装+登录+使用,含所有版本,2026最新)
Codex是OpenAI推出的开源AI编程智能体,本地运行,可理解整个代码库,支持自然语言指令改代码、执行命令、跑测试、修Bug,兼容Win/macOS/Linux。(239字)
8044 58
|
3天前
|
弹性计算 人工智能 API
Codex超详细入门指南(下载·安装·登录·上手,全版本覆盖,2026最新版)
建议收藏本教程,2026 全年各版本更新随时回来查阅。如果你在搭建过程中遇到任何问题,欢迎结合 阿里云工单系统 提交技术支持请求,或在 阿里云开发者社区 搜索 Codex 相关话题交流。 祝你编码愉快,效率翻倍!
1533 1
|
6天前
|
JSON 前端开发 API
阿里云最新Qwen4-Max大模型介绍:模型定位、特征、能力、适用场景解析
2026 年 11 月 11 日,阿里发布第四代旗舰模型Qwen4-Max预览版,首发千问 AI 平台 Token Plan,并同步接入千问办公、Qoder 等入口。该版本聚焦知识理解、世界感知、编程与 Agentic 四项升级,主打复杂编程、专业办公、前端设计与专业软件操作。预览期至 11 月 25 日 24:00,到期后模型标识下线;限时 2 折、新用户再享 5 折,最低 1 折可体验。
|
19天前
|
JavaScript API iOS开发
DeepSeek Harness下载、安装、配置一篇搞定(2026整理,送常用插件)
DeepSeek Harness(DSH)是DeepSeek于2026年开源的MIT协议AI Agent框架,支持插件化组装模型、工具、沙箱与UI,兼容主流大模型。本文提供免Node.js的桌面端安装包(Win/macOS),含详细图文教程及热门插件推荐。
5725 69
|
6天前
|
云安全 人工智能 安全
|
13天前
|
Linux 开发工具 iOS开发
2026最新codex下载安装保姆级使用教程(下载+安装+登录+使用,含所有历史版本)
本文详解OpenAI Codex国内快速上手指南:提供Win/macOS/Linux全平台免安装包、npm/Homebrew等多方式安装、账号/API Key双登录、简体中文切换,覆盖下载、安装、汉化、使用及高频避坑(如微软商店失败、npm超时等),10分钟即可跑通。
2954 9
|
6天前
|
人工智能 前端开发 API
阿里云Qwen4-Max 大模型详解:定位、特征、能力、适用场景与相对Qwen3-Max差异解析
2026年11月11日,阿里发布第四代旗舰模型Qwen4-Max预览版,首发千问AI平台Token Plan并接入千问办公、Qoder等入口。该版本聚焦知识理解、世界感知、编程与Agentic四项升级,主打复杂编程、专业办公、前端设计与专业软件操作等真实任务。预览期为11月11日10:00至11月25日24:00,仅支持Token Plan调用,到期后模型标识下线;限时2折、新用户再享5折,最低1折可体验。
|
3天前
|
Linux Go 开发工具
手机上跑 DeepSeek 智能体:开源安卓客户端 DSH Go 安装与使用指南
DSH Go 是一款开源安卓客户端,将 DeepSeek Harness 智能体引擎装进手机:免 Root、免 Termux,一键安装即用;支持本机运行(内置 Ubuntu+Node.js)或远程接管电脑会话;具备插话打断、过程折叠、屏幕操控、端到端加密分享等特色功能,真正实现智能体“口袋化”。
2340 0
|
11天前
|
人工智能 安全 API
DeepSeek Harness下载、安装、配置一篇搞定(2026整理,送常用插件)
DeepSeek Harness(dsh)是DeepSeek AI于2026年开源的轻量级Agent运行框架,基于Cordis内核,践行“一切皆插件”理念。支持Web/桌面双端,开箱即用;内置多模型接入、丰富插件生态(超3.5万),适配编程、办公、创作等场景。(239字)
1889 1