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搜索」全面对比!斯坦福华人博士纯手工标注:新必应流畅度最低,近一半句子都没引用
246 0
|
7月前
|
人工智能 IDE Linux
chatgpt的ai编程工具
该内容是关于两个chatgpt的ai编程工具的安装和使用说明。Copilot的下载步骤包括在IDE的设置中搜索并安装插件,然后重启IDE并登录GitHub账户。使用时,通过写注释触发建议,用快捷键选择建议。启用或禁用Copilot可通过底部状态图标。另一个工具是Alibaba Cloud AI Coding Assistant (Cosy),同样在IDE的插件市场下载安装后重启。其详细使用方法建议参考官网。
302 0
|
4月前
|
人工智能 自然语言处理 搜索推荐
chatgpt这么火,现在AI搜索引擎有哪些呢?
国外AI搜索引擎包括ChatGPT,擅长自然语言处理与内容生成;Google Bard,提供智能个性化搜索体验;Microsoft Bing集成GPT模型增强智能检索;Perplexity AI以简洁答案及文献引用著称;Neeva强调隐私保护与无广告服务。国内方面,天工AI支持多种功能如知识问答与代码编程;腾讯元宝基于混元模型助力内容创造与学习;360AI搜索以精准全面的信息搜索见长;秘塔AI专注提升写作质量和效率;开搜AI搜索提供个性化智能搜索服务。以上引擎均利用先进AI技术提升用户体验。更多详情参阅[AI搜索合集](zhangfeidezhu.com/?page_id=651)。
117 8
chatgpt这么火,现在AI搜索引擎有哪些呢?
|
4月前
|
机器学习/深度学习 人工智能 自然语言处理
HuggingGPT解析:使用 ChatGPT及HuggingFace上的族系解决AI问题
HuggingGPT是一个框架,它使用大型语言模型(如ChatGPT)作为控制器来管理和协调Hugging Face上的AI模型,以语言作为通用接口解决多模态和领域的复杂AI任务。
66 0
HuggingGPT解析:使用 ChatGPT及HuggingFace上的族系解决AI问题
|
4月前
|
机器学习/深度学习 人工智能 算法
为什么ChatGPT等AI大模型都是基于Python开发?
为什么ChatGPT等AI大模型都是基于Python开发?
|
4月前
|
人工智能 自然语言处理 Linux
免费ChatGPT4o灵办AI可体验浏览器插件
灵办AI就是您所需的最佳助手!我们为您带来了一款多功能AI工具,ChatGPT4o不仅能为您提供精准翻译,还能满足您的对话需求、智能续写、AI搜索、文档阅读、代码生成与修正等多种需求。灵办 AI,真正让工作和学习变得轻松高效!一款多功能智能助手,旨在提升工作和学习效率。它提供实时翻译、对话问答、搜索、写作和网页阅读等服务,支持多种浏览器和操作系统,帮助用户随时获取信息,打破语言障碍,优化内容创作和信息处理。
124 0
|
4月前
|
Web App开发 人工智能 安全
Gemini vs ChatGPT:谷歌最新的AI和ChatGPT相比,谁更强?
Gemini vs ChatGPT:谷歌最新的AI和ChatGPT相比,谁更强?
|
4月前
|
人工智能 安全 机器人
ChatGPT 1岁:创新、争议和AI产生突破的一年
ChatGPT 1岁:创新、争议和AI产生突破的一年
|
6月前
|
人工智能 安全 机器人
ChatGPT 1岁:创新、争议和AI产生突破的一年
ChatGPT 1岁:创新、争议和AI产生突破的一年
|
6月前
|
人工智能 机器人 API
OpenAI发布新AI模型GPT-4o和桌面版ChatGPT
OpenAI发布新AI模型GPT-4o和桌面版ChatGPT

热门文章

最新文章