ChatGPT,为啥写二分搜索容易死循环?

简介: ChatGPT,为啥写二分搜索容易死循环?

背景

这段时间ChatGPT在码农界,引起了不小轰动,最热的话题中有一个与程序员息息相关,它会写代码那程序员是不是会集体下岗?刚好最近听说了这么一句话,“90%程序员都写不对二分搜索”,那就整个二分搜索最常见的问题考考ChatGPT


了不起:为什么写二分搜索容易死循环?

ChatGPT:一个常见的原因是在二分搜索中没有正确处理边界情况,例如:

1、非递归实现中,循环终止条件可能不正确,导致死循环;

2、递归实现中,递归条件可能不正确,导致无限递归。

此外,当待搜索的数组不是有序时,也可能导致搜索结果不正确或死循环。如果你遇到了这个问题,可以仔细检查你的代码并尝试调试。可以使用打印语句或者调试器来寻找问题所在。同时,你也可以参考其他人的代码或者算法实现,再次检查你的思路是否正确。


了不起觉得,还算是一个中规中矩的答案,并没有十分惊艳,不过也讲到了关键所在就是条件处理。

随后让它给出一个二分搜索的代码,也与搜索引擎提供基本一致,没有系统的对二分问题做出分类,以下了不起总结的普通二分和不等式二分,几乎涵盖了所有的二分问题的方法论。

一、普通二分搜索

普通的二分搜索,就不再赘述,属于基本功了,现在的大多数算法面试也基本不再问。

1.1 编码实战

public class _1_BinarySearch {
    public int basicBinarySearch(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return -1;
    }
}

1.2 注意点

实数的二分就不用考虑所谓的mid+1和mid-1,因为index是整数是离散的,不是连续精确的,变更区间条件时出现死循环。

二、不等式二分搜索

2.1 三步走

1、写出二分的条件,需要满足的条件,包含mid的branch;

2、条件放到if,确定要求满足条件的mid的min(right = mid)或者max(left = mid);

3、else left = mid + 1 或 right = mid - 1,后者需要在mid取值的时候补上+1。

2.2 注意点

mid取值补上1,是为了防止死循环,当left和right为5和6时,模拟想想。

前驱和后继和条件本身无关,与是否满足条件相关,如果是满足求min即是后继。

需要考虑如何表示无解?前驱left = -1,表示无解;后继right= n,表示无解。

2.3 编码实战

一段有序的数组但是有重复数组,搜索出目标数字的index区间。

public class _1_BinarySearch {
    public int[] searchRange(int[] nums, int target) {
        int leftBound = leftBound(nums, target);
        int rightBound = rightBound(nums, target);
        if (leftBound > rightBound) {
            return new int[]{-1, -1};
        }
        return new int[]{leftBound, rightBound};
    }
    // 前驱型往前找
    int rightBound(int[] nums, int target) {
        int left = -1;
        int right = nums.length - 1;
        while (left < right) {
            int mid = (left + right + 1) / 2;
            if (nums[mid] <= target) {
                left = mid; // max 向右扩张
            } else {
                right = mid - 1;
            }
        }
        return left;
    }
    // 后继型往后找
    int leftBound(int[] nums, int target) {
        int left = 0;
        int right = nums.length;
        while (left < right) {
            int mid = (left + right) / 2;
            // 条件考虑了nums[mid],即func(mid)的递增递减关系,需要满足这个条件
            if (nums[mid] >= target) {
                right = mid; // min 向左收缩
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}

小结

1、以上二分搜索,对于mid是否溢出均未处理,如果给了数据集接近int的max,那么可以这么取mid = left + (right - left) / 2。

2、不等式二分搜索,属于常考的题目了,用于求取一些难解问题的最优值,这些难解的问题都有一个特点,问题可以转化成判定问题,这时候就可以二分的条件求值。

相关文章
|
自然语言处理 搜索推荐
4款「ChatGPT搜索」全面对比!斯坦福华人博士纯手工标注:新必应流畅度最低,近一半句子都没引用
4款「ChatGPT搜索」全面对比!斯坦福华人博士纯手工标注:新必应流畅度最低,近一半句子都没引用
303 0
|
2月前
|
机器学习/深度学习 人工智能 文字识别
浏览器AI模型插件下载,支持chatgpt、claude、grok、gemini、DeepSeek等顶尖AI模型!
极客侧边栏是一款浏览器插件,集成ChatGPT、Claude、Grok、Gemini等全球顶尖AI模型,支持网页提问、文档分析、图片生成、智能截图、内容总结等功能。无需切换页面,办公写作效率倍增。内置书签云同步与智能整理功能,管理更高效。跨平台使用,安全便捷,是AI时代必备工具!
169 8
|
7月前
|
人工智能 Linux API
Omnitool:开发者桌面革命!开源神器一键整合ChatGPT+Stable Diffusion等主流AI平台,本地运行不联网
Omnitool 是一款开源的 AI 桌面环境,支持本地运行,提供统一交互界面,快速接入 OpenAI、Stable Diffusion、Hugging Face 等主流 AI 平台,具备高度扩展性。
743 94
Omnitool:开发者桌面革命!开源神器一键整合ChatGPT+Stable Diffusion等主流AI平台,本地运行不联网
|
8月前
|
机器学习/深度学习 人工智能 搜索推荐
哈佛推出全新类ChatGPT癌症诊断AI,登上Nature!准确率高达96%
哈佛大学研究团队开发的新型AI模型CHIEF,在《自然》期刊发表,癌症诊断准确率达96%。CHIEF基于深度学习,能自动识别、分类癌症并预测生存期,具高准确性、多任务能力和泛化性。它结合病理图像与基因组学等数据,显著提升诊断效率和个性化治疗水平,有望改善医疗资源不平等。但数据隐私和临床效果验证仍是挑战。论文见:https://www.nature.com/articles/s41586-024-07894-z
297 101
|
6月前
|
人工智能 编解码 运维
当ChatGPT能写情书、Sora会造电影:我们必须掌握的AI内容识别技能
随着AI技术迅猛发展,AI生成内容在文学、新闻、绘画等领域广泛应用,但其真假难辨、质量参差不齐,可能带来信息误导、知识产权侵犯及安全风险等问题。学会识别AI生成内容至关重要,包括通过逻辑漏洞排查、语言风格分析、生物特征异常检测等手段审核文本、图片和视频。人工审核在面对高隐蔽性内容时仍不可替代,需结合工具与上下文理解共同筑起防护屏障。守护真实信息、规避风险,是每个人在AI时代应尽的责任。
164 7
|
7月前
|
存储 人工智能 API
ChatGPT-on-WeChat:Star32.4k, DeepSeek加持!这款开源神器秒变AI助手,聊天体验直接起飞!
嗨,大家好,我是小华同学。今天为大家介绍一款结合DeepSeek引擎的开源项目——ChatGPT-on-WeChat,由开发者zhayujie打造。它将微信变成智能AI助手,支持文本、图片、语音对话,具备定时提醒、天气查询等扩展功能,完全开源且易于定制。项目地址:https://github.com/zhayujie/chatgpt-on-wechat。关注我们,获取更多优质开源项目和高效学习方法。
620 11
|
7月前
|
人工智能 自然语言处理 算法
DeepSeek vs ChatGPT:AI对决中的赢家是……人类吗?
DeepSeek VS ChatGPT:DeepSeek以开源黑马姿态崛起,凭借低成本、高性能的「DeepSeek-V3」和专为深度推理设计的「DeepSeek-R1」,成为中小开发者的首选。而ChatGPT则较贵。 然而,AI依赖也带来隐忧,长期使用可能导致记忆衰退和“脑雾”现象。为此,推荐Neuriva解决方案,专注力提升30%,记忆留存率提升2.1倍,助力人类在AI时代保持脑力巅峰。 DeepSeek赢在技术普惠,ChatGPT胜于生态构建,人类的关键在于平衡AI与脑力健康,实现“双核驱动”突破极限!
598 7
|
9月前
|
人工智能 搜索推荐 iOS开发
OpenAI推出适用于iPhone的ChatGPT,与Apple实现具有里程碑意义的AI整合
OpenAI推出适用于iPhone的ChatGPT,与Apple实现具有里程碑意义的AI整合
|
人工智能 自然语言处理 搜索推荐
chatgpt这么火,现在AI搜索引擎有哪些呢?
国外AI搜索引擎包括ChatGPT,擅长自然语言处理与内容生成;Google Bard,提供智能个性化搜索体验;Microsoft Bing集成GPT模型增强智能检索;Perplexity AI以简洁答案及文献引用著称;Neeva强调隐私保护与无广告服务。国内方面,天工AI支持多种功能如知识问答与代码编程;腾讯元宝基于混元模型助力内容创造与学习;360AI搜索以精准全面的信息搜索见长;秘塔AI专注提升写作质量和效率;开搜AI搜索提供个性化智能搜索服务。以上引擎均利用先进AI技术提升用户体验。更多详情参阅[AI搜索合集](zhangfeidezhu.com/?page_id=651)。
408 8
chatgpt这么火,现在AI搜索引擎有哪些呢?
|
机器学习/深度学习 人工智能 自然语言处理
HuggingGPT解析:使用 ChatGPT及HuggingFace上的族系解决AI问题
HuggingGPT是一个框架,它使用大型语言模型(如ChatGPT)作为控制器来管理和协调Hugging Face上的AI模型,以语言作为通用接口解决多模态和领域的复杂AI任务。
332 0
HuggingGPT解析:使用 ChatGPT及HuggingFace上的族系解决AI问题