首页 > 其他分享 >1-数组-11-二分查找-LeetCode704

1-数组-11-二分查找-LeetCode704

时间:2024-05-24 19:18:08浏览次数:28  
标签:11 二分 right target nums LeetCode704 middle 目标值 left

1-数组-11-二分查找-LeetCode704

参考:代码随想录

LeetCode:题目序号35

更多内容欢迎关注我(持续更新中,欢迎Star✨)

Github:CodeZeng1998/Java-Developer-Work-Note

技术公众号:CodeZeng1998(纯纯技术文)

生活公众号:好锅(Life is more than code)

博客园: CodeZeng1998

其他平台:CodeZeng1998好锅

题目描述:

给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1

示例 1:

输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4

示例 2:

输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1

提示:

  1. 你可以假设 nums 中的所有元素是不重复的。
  2. n 将在 [1, 10000]之间。
  3. nums 的每个元素都将在 [-9999, 9999]之间。

二分查找(左闭右闭)

    /**
     * 二分查找(左闭右闭)
     *
     * @param nums 升序排序的数组
     * @param target 目标值
     * @return 数组索引,如果未找到则返回 -1
     * @Author: CodeZeng1998
     */
    public int binarySearch(int[] nums, int target) {

        if (target < nums[0] || target > nums[nums.length - 1]) {
            return -1;
        }

        int left = 0;
        int right = nums.length - 1;

        while (left <= right) {
            // 当 left、right为较大整数时可能出现溢出,防止溢出,等同于(left + right)/2
            int middle = left + ((right - left) >> 1);

            if (nums[middle] > target) {
                right = middle - 1;
            } else if (nums[middle] < target) {
                left = middle + 1;
            } else {
                return middle;
            }
        }

        return -1;
    }

ChatGPT:

这段代码实现了一个二分查找算法,用于在升序排序的数组中查找目标值。以下是代码的解释:

  • nums:升序排序的整数数组。
  • target:要查找的目标值。
  • 方法返回目标值在数组中的索引,如果未找到则返回 -1。

算法步骤如下:

  1. 首先,检查目标值是否小于数组的第一个元素或大于数组的最后一个元素,如果是,则返回 -1,因为目标值不可能存在于数组中。
  2. 使用两个指针 leftright 分别指向数组的开头和结尾。
  3. 进入循环,当 left 小于等于 right 时进行查找。
  4. 计算中间索引 middle,采用了防止整数溢出的方式计算,即 left + ((right - left) >> 1)
  5. 如果 nums[middle] 大于目标值 target,则更新 rightmiddle - 1,因为目标值可能在左半部分。
  6. 如果 nums[middle] 小于目标值 target,则更新 leftmiddle + 1,因为目标值可能在右半部分。
  7. 如果 nums[middle] 等于目标值 target,则直接返回 middle,表示找到了目标值的索引。
  8. 如果循环结束仍未找到目标值,则返回 -1,表示未找到目标值。

这个算法的时间复杂度为 O(log n),其中 n 是数组的长度,因为每次查找都将搜索范围减半。

二分查找(左闭右开)

    /**
     * 二分查找(左闭右开)
     *
     * @param nums 升序排序的数组
     * @param target 目标值
     * @return 数组索引,如果未找到则返回 -1
     * @author CodeZeng1998
     */
    public int binarySearch(int[] nums, int target) {
        int left = 0;
        // 定义target在左闭右开的区间里,即:[left, right)
        int right = nums.length;

        // 因为left == right的时候,在[left, right)是无效的空间,所以使用 <
        while (left < right) {
            // 当 left、right为较大整数时可能出现溢出,防止溢出,等同于(left + right)/2
            int middle = left + ((right - left) >> 1);

            if (nums[middle] > target) {
                right = middle;
            } else if (nums[middle] < target) {
                left = middle + 1;
            } else {
                return middle;
            }
        }

        return -1;
    }

GhatGPT:

这段代码实现了一个二分查找算法,与之前的代码相比,不同之处在于区间的定义是左闭右开的 [left, right),而不是左闭右闭的 [left, right]。以下是代码的解释:

  • nums:升序排序的整数数组。
  • target:要查找的目标值。
  • 方法返回目标值在数组中的索引,如果未找到则返回 -1。

算法步骤如下:

  1. 定义两个指针 leftright,分别指向数组的开头和结尾(但是 right 指向的是无效的位置,即数组最后一个元素的下一个位置)。
  2. 进入循环,当 left 小于 right 时进行查找。
  3. 计算中间索引 middle,采用了防止整数溢出的方式计算,即 left + ((right - left) >> 1)
  4. 如果 nums[middle] 大于目标值 target,则更新 rightmiddle,因为目标值可能在左半部分,但是 middle 不包含在搜索范围内。
  5. 如果 nums[middle] 小于目标值 target,则更新 leftmiddle + 1,因为目标值可能在右半部分。
  6. 如果 nums[middle] 等于目标值 target,则直接返回 middle,表示找到了目标值的索引。
  7. 如果循环结束仍未找到目标值,则返回 -1,表示未找到目标值。

这个算法与之前的算法相比,在终止条件和区间的定义上有所不同,但是原理和时间复杂度仍然是相同的,都是 O(log n)。

Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.

You must write an algorithm with O(log n) runtime complexity.

Example 1:

Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 exists in nums and its index is 4

Example 2:

Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1
Explanation: 2 does not exist in nums so return -1

Constraints:

  • 1 <= nums.length <= 104
  • -104 < nums[i], target < 104
  • All the integers in nums are unique.
  • nums is sorted in ascending order.

更多内容欢迎关注我(持续更新中,欢迎Star✨)

Github:CodeZeng1998/Java-Developer-Work-Note

技术公众号:CodeZeng1998(纯纯技术文)

生活公众号:好锅(Life is more than code)

博客园: CodeZeng1998

其他平台:CodeZeng1998好锅

标签:11,二分,right,target,nums,LeetCode704,middle,目标值,left
From: https://www.cnblogs.com/codezeng1998/p/18203219

相关文章

  • OFDM 802.11a的FPGA实现(二十二)DAC模块(含代码)
    目录1.前言2.实现思路3.verilog代码4.MoselSim仿真完整工程链接(含verilog和Matlab代码):OFDM802.11a的xilinxFPGA实现1.前言上一节完成了MUC模块,实现了对MAC层进行数据交互,以及控制物理层各个模块的工作。现在还剩下最后一个DAC模块,作用是将时域的输出按照前导码、sig......
  • 折叠 MacBook 价格或比肩 Vision Pro;必应全球宕机波及 ChatGPT 丨RTE 开发者日报 Vol.
      开发者朋友们大家好: 这里是「RTE开发者日报」,每天和大家一起看新闻、聊八卦。我们的社区编辑团队会整理分享RTE(RealTimeEngagement)领域内「有话题的新闻」、「有态度的观点」、「有意思的数据」、「有思考的文章」、「有看点的会议」,但内容仅代表编辑的个人观点,......
  • 图论-二分图匹配匈牙利算法
    不得不说,如果以现实角度代入此算法的理解,就合理了很多,虽然有悖道德准则重点在于以下几点每次给女生分配男生前,都把男生全部初始化为可预定状态(即使他已经被别人成功匹配了)在所有女生中意的男生中遍历,如果发现该男生可预订就先预定,然后看他是否已经有主了,如果有主了,就dfs(matc......
  • 代码随想录算法训练营第一天 | 704.二分查找;27. 移除元素
    代码随想录算法训练营第一天|704.二分查找(红蓝模板法);27.移除元素(双指针法)704题链接:https://leetcode.cn/problems/binary-search/description/二分查找:https://programmercarl.com/0704.二分查找.html#其他语言版本二分查找红蓝法笔记:二分查找为什么总是写错?_哔哩哔哩_bil......
  • 二分查找
    二分查找的写法(有两种,这里只记录第一种): 如果区间是[a,b],即可以取到low、high,则mid=(low+high)/2:1.while(low<=high){..},注意此处是"<="2.if(v[mid]<target){low++;}3.if(v[mid]>target){high--;}这里条件控制一定要明确:<=、low++、high--。补充:while(low<=h......
  • git之fatal: unable to access ‘https://11.2.7.8:68/mjgn/mj.git/‘: SSL certifica
    MENU前言方法一方法二方法三方法四结束语前言出现这个错误是因为Git在访问仓库时遇到了SSL证书问题,具体是证书的密钥太弱,不符合安全要求。方法一升级或更换SSL证书联系服务器管理员,确保服务器上使用的是强密钥SSL证书。推荐使用至少2048位的密钥。方法二......
  • 第11章.创建MDK工程-基于自建库函数
    目录0.《STM32单片机自学教程》专栏11.1基于库函数的开发方式11.2构建自己的库函数11.2.1外设寄存器结构体定义0.《STM32单片机自学教程》专栏        本文作为专栏《STM32单片机自学教程》专栏其中的一部分,返回专栏总纲,阅读所有文章,点击Link:  STM32......
  • 1116:最长平台
    1116:最长平台时间限制:1000ms      内存限制:65536KB提交数:115620   通过数: 40570【题目描述】已知一个已经从小到大排序的数组,这个数组的一个平台(Plateau)就是连续的一串值相同的元素,并且这一串元素不能再延伸。例如,在 1,2,2,3,3,3,4,5,5,6中1,2-2,3-3-3,4,5-5,6......
  • 洛谷[普及]:P1149 [NOIP2008 提高组] 火柴棒等式
    [NOIP2008提高组]火柴棒等式感谢题目提供者CCF_NOI题目描述给你n 根火柴棍,你可以拼出多少个形如A+B=C 的等式?等式中的A、B、C 是用火柴棍拼出的整数(若该数非零,则最高位不能是0)。用火柴棍拼数字 的拼法如图所示:注意:1.加号与等号各自需要两根火柴棍;2.如果,则......
  • CVE-2020-11981
    ApacheAirflowCelery消息中间件命令执行(CVE-2020-11981)ApacheAirflow是一款开源的,分布式任务调度框架。在其1.10.10版本及以前,如果攻击者控制了Celery的消息中间件(如Redis/RabbitMQ),将可以通过控制消息,在Worker进程中执行任意命令。漏洞环境依次执行如下命令启动airflow1.1......