【Java算法】二分查找 下

    🔥个人主页： 中草药

🔥专栏：【算法工作坊】算法实战揭秘

一.山脉数组的峰顶索引

题目链接：852.山脉数组的峰顶

​

算法原理

        这段代码实现了一个查找山峰数组中峰值索引的算法。山峰数组是一个先递增后递减的数组，即存在一个索引 i 使得对于所有的 j < i，有 arr[j] < arr[j + 1]，且对于所有的 k > i，有 arr[k] > arr[k - 1]。这个索引 i 就是峰值的索引。

        算法使用了二分查找(Binary Search)的方法来寻找峰值索引。其核心思想是在数组中寻找拐点（即峰值），在该点左侧的值小于右侧的值，在右侧则相反。由于数组是先升后降的，这个拐点就是我们所要找的峰值。

具体分析如下：

  1. 初始化两个指针 left 和 right，分别指向数组的第二个元素和倒数第二个元素。这是因为数组的第一个和最后一个元素不可能是峰值。

  2. 在 while 循环中，计算中间位置 mid。这里使用 (left + (right - left + 1)) / 2 而不是常见的 (left + right) / 2 来避免可能的整数溢出，并确保 mid 总是指向 left 和 right 之间的元素，包括边界上的元素。

  3. 如果 arr[mid] 大于 arr[mid - 1]，说明 mid 可能是峰值或者峰值在 mid 的右边，因此将 left 更新为 mid。

  4. 否则，如果 arr[mid] 小于或等于 arr[mid - 1]，说明峰值在 mid 的左边，因此将 right 更新为 mid - 1。

  5. 当 left 和 right 相遇时，循环结束，此时 left 指向的位置就是峰值的索引。

这种算法的时间复杂度是 O(log n)，其中 n 是数组的长度，因为每次迭代都将搜索范围减半。这比线性搜索的 O(n) 时间复杂度要高效得多。

代码

 public int peakIndexInMountainArray(int[] arr) {int left=1,right=arr.length-2;while(left<right){int mid=left+(right-left+1)/2;if(arr[mid]>arr[mid-1]){left=mid;}else{right=mid-1;}}return left;}

举例 

测试用例 arr = [0,10,5,2]

首先，初始化 left = 1 和 right = arr.length - 2 = 2。

接下来，我们进入 while 循环：

  1. 第一次循环：

    • left = 1, right = 2
    • 计算 mid = left + (right - left + 1) / 2 = 1 + (2 - 1 + 1) / 2 = 2
    • 检查 arr[mid] 是否大于 arr[mid - 1]，也就是检查 arr[2] 是否大于 arr[1]。由于 arr[2] = 5 并不大于 arr[1] = 10，条件不满足。
    • 所以，我们将 right 更新为 mid - 1，即 right = 1。

  2. 这时，left 和 right 都指向同一个位置 1，循环条件 left < right 不再满足，循环结束。

最后，返回 left 的值，即 1。这意味着数组中的峰值位于索引 1 上，这与给定数组 [0, 10, 5, 2] 的实际情况相吻合，因为最大值 10 确实位于索引 1。

所以，这段代码正确地找到了山峰数组的峰值索引。

 二.寻找峰值

题目链接：162.寻找峰值

​

算法原理

        同样使用了二分查找(Binary Search)算法来找到所谓的“峰值元素”。峰值元素定义为一个元素，它严格大于它的邻居。注意，数组可以是未排序的，并且数组的两端被认为是邻居元素的“虚拟”较小值，这样数组的起始元素和末尾元素也可以成为峰值元素。

算法的步骤如下：

  1. 初始化两个指针 left 和 right，分别指向数组的起始位置 0 和终止位置 nums.length - 1。

  2. 进入 while 循环，只要 left 小于 right，表示搜索区间内还有多个元素需要考虑。

  3. 在循环内部，计算中间位置 mid。这里使用 (left + (right - left) / 2) 来避免整数溢出，并确保 mid 总是落在 left 和 right 之间。

  4. 比较 nums[mid] 和 nums[mid + 1] 的大小。如果 nums[mid] 小于 nums[mid + 1]，那么峰值一定不在 mid 及其左侧，因为从 mid 到 mid + 1 数组是上升的。这时，将 left 更新为 mid + 1。

  5. 否则，如果 nums[mid] 大于或等于 nums[mid + 1]，那么峰值可能在 mid 或者其左侧。这时，将 right 更新为 mid。

  6. 当 left 和 right 相遇时，循环结束，此时 left 指向的位置就是峰值元素的索引。这是因为当 left == right 时，它们共同指向的元素必定是峰值，因为在之前的迭代中，我们总是排除了较小的邻居元素所在的那一边。

这段代码的时间复杂度同样是 O(log n)，其中 n 是数组的长度，因为每次迭代都将搜索范围减半，这使得算法非常高效。

代码

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

举例 

测试用例 [1,2,1,3,5,6,4]

我们开始分析：

  1. 初始化 left = 0 和 right = nums.length - 1 = 6。

  2. 第一次循环：

    • mid = left + (right - left) / 2 = 0 + (6 - 0) / 2 = 3
    • 检查 nums[mid] 和 nums[mid + 1]，即 nums[3] 和 nums[4]，比较 3 和 5。
    • 因为 nums[3] 小于 nums[4]，所以更新 left 为 mid + 1，即 left = 4。

  3. 第二次循环：

    • 此时 left = 4 和 right = 6。
    • mid = left + (right - left) / 2 = 4 + (6 - 4) / 2 = 5
    • 检查 nums[mid] 和 nums[mid + 1]，即 nums[5] 和 nums[6]，比较 6 和 4。
    • 因为 nums[5] 不小于 nums[6]，所以更新 right 为 mid，即 right = 5。

  4. 第三次循环：

    • 现在 left = 4 和 right = 5。
    • mid = left + (right - left) / 2 = 4 + (5 - 4) / 2 = 4
    • 检查 nums[mid] 和 nums[mid + 1]，即 nums[4] 和 nums[5]，比较 5 和 6。
    • 因为 nums[4] 小于 nums[5]，所以更新 left 为 mid + 1，即 left = 5。

  5. 第四次循环：

    • 此时 left = 5 和 right = 5。
    • 因为 left 等于 right，while 循环的条件不再满足，循环结束。

最终，函数返回 left 的值，即 5。这表明数组 [1, 2, 1, 3, 5, 6, 4] 中的一个峰值元素位于索引 5，其值为 6。值得注意的是，根据题目的定义，可能有多个峰值元素，而算法保证返回的是其中一个。在这个例子中，索引 1 (nums[1] = 2) 和索引 5 (nums[5] = 6) 都是合法的峰值元素。

三.寻找旋转排序数组的最小值

题目链接：153.寻找旋转排序数组的最小值

​ 

算法原理

        这段代码实现了一个算法，用于在一个旋转排序数组中找到最小元素。旋转排序数组指的是原本有序的数组经过若干次旋转得到的结果。例如，数组 [1, 2, 3, 4, 5] 经过旋转可能变成 [3, 4, 5, 1, 2]。

        算法的原理基于二分查找(Binary Search)，但是针对旋转排序数组进行了调整。关键在于利用旋转特性来缩小搜索范围。旋转数组的最小元素位于旋转点之后，旋转点之前的子数组是递增的，旋转点之后的子数组也是递增的，但整个数组的顺序被打乱。

算法步骤如下：

  1. 初始化 left 和 right 分别指向数组的起始和末尾位置。

  2. 获取数组最后一个元素 x 作为基准值。这是因为在旋转数组中，最后一个元素通常是未旋转前数组的最后一个元素，或者是旋转后新数组的最大值。

  3. 进入 while 循环，只要 left < right，就说明搜索空间大于1个元素。

  4. 计算中间位置 mid，使用 (left + (right - left) / 2) 来避免整数溢出问题。

  5. 比较 nums[mid] 和 x 的大小：

    • 如果 nums[mid] > x，说明 mid 位于旋转点的左侧递增子数组中，最小值只能在 mid 右侧的子数组中，因此更新 left 为 mid + 1。
    • 否则，nums[mid] <= x，说明 mid 位于旋转点的右侧递增子数组中，或者正好位于旋转点上，最小值可能在 mid 或者左侧子数组中，因此更新 right 为 mid。

  6. 当 left 和 right 相遇时，循环结束，此时 left 指向的位置就是最小元素的索引，返回 nums[left] 即可得到最小值。

此算法的时间复杂度为 O(log n)，其中 n 是数组的长度，因为它在每一步都有效地将搜索空间减半。这使得算法在处理大数据量时非常高效。

代码

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

举例 

测试用例 nums = [4,5,6,7,0,1,2]

我们开始逐步分析：

  1. 初始化 left = 0 和 right = nums.length - 1 = 6。
  2. 设置 x = nums[right] = nums[6] = 2。

第一次循环：

  • mid = left + (right - left) / 2 = 0 + (6 - 0) / 2 = 3
  • 检查 nums[mid] 和 x，即 nums[3] 和 2，比较 7 和 2。
  • 因为 nums[mid] 大于 x，更新 left 为 mid + 1，即 left = 4。

第二次循环：

  • 此时 left = 4 和 right = 6。
  • mid = left + (right - left) / 2 = 4 + (6 - 4) / 2 = 5
  • 检查 nums[mid] 和 x，即 nums[5] 和 2，比较 1 和 2。
  • 因为 nums[mid] 不大于 x，更新 right 为 mid，即 right = 5。

第三次循环：

  • 此时 left = 4 和 right = 5。
  • mid = left + (right - left) / 2 = 4 + (5 - 4) / 2 = 4
  • 检查 nums[mid] 和 x，即 nums[4] 和 2，比较 0 和 2。
  • 因为 nums[mid] 不大于 x，更新 right 为 mid，即 right = 4。

第四次循环：

  • 现在 left = 4 和 right = 4。
  • while 循环的条件 left < right 不再满足，循环结束。

最终，函数返回 nums[left] 的值，即 nums[4]，结果为 0。

这表明数组 [4, 5, 6, 7, 0, 1, 2] 中的最小元素为 0，位于索引 4。此算法成功找到了旋转排序数组中的最小元素。

四.LCR 173.点名 

题目链接：LCR 173.点名

​

算法原理

  1. 初始化两个指针 left 和 right，分别指向数组的起始位置 0 和终止位置 records.length - 1。

  2. 使用 while 循环，只要 left < right，意味着数组中还可能存在不匹配的情况。

  3. 计算中间位置 mid，使用 (left + (right - left) / 2) 来避免整数溢出。

  4. 检查 mid 位置的元素是否等于 mid：

    • 如果 records[mid] 等于 mid，这意味着 mid 位置的值与索引匹配，因此缺失的元素可能在 mid 的右侧。更新 left 为 mid + 1。
    • 否则，如果 records[mid] 不等于 mid，这可能是由于缺失的元素在 mid 的位置应该出现，但实际没有出现。因此，更新 right 为 mid，继续在左侧查找。

  5. 当 left 和 right 相遇时，循环结束。此时，left 指向的位置要么是缺失元素应该出现的位置，要么紧随其后。

  6. 最后，检查 left 位置的元素是否等于 left：

    • 如果 left 位置的元素等于 left，这意味着 left 位置的元素没有缺失，因此缺失的元素应该是 left + 1。
    • 否则，left 位置的元素小于 left，这意味着 left 位置的元素是缺失的，因此缺失的元素就是 left。

时间复杂度为 O(log n)，其中 n 是数组的长度，因为算法使用了二分查找，每次迭代都将搜索范围减半。

这种算法特别适用于数据量大、有序或部分有序的数组中查找缺失的元素，效率远高于线性查找。

代码

public int takeAttendance(int[] records) {int left=0,right=records.length-1;while(left<right){int mid=left+(right-left)/2;if(mid==records[mid]){left=mid+1;}else{right=mid;}}//判断特殊情况，如[0,1,2,3,4,5]此时缺少的值应该是6if(left==records[left]){return left+1;}return left;}

举例 

测试用例 records = [0, 1, 2, 3, 4, 5, 6, 8]

我们开始逐步分析：

  1. 初始化 left = 0 和 right = records.length - 1 = 7。

第一次循环：

  • mid = left + (right - left) / 2 = 0 + (7 - 0) / 2 = 3
  • 检查 records[mid] 和 mid，即 records[3] 和 3，比较 3 和 3。
  • 因为 records[mid] 等于 mid，更新 left 为 mid + 1，即 left = 4。

第二次循环：

  • 此时 left = 4 和 right = 7。
  • mid = left + (right - left) / 2 = 4 + (7 - 4) / 2 = 5
  • 检查 records[mid] 和 mid，即 records[5] 和 5，比较 5 和 5。
  • 因为 records[mid] 等于 mid，更新 left 为 mid + 1，即 left = 6。

第三次循环：

  • 此时 left = 6 和 right = 7。
  • mid = left + (right - left) / 2 = 6 + (7 - 6) / 2 = 6
  • 检查 records[mid] 和 mid，即 records[6] 和 6，比较 6 和 6。
  • 因为 records[mid] 等于 mid，更新 left 为 mid + 1，即 left = 7。

第四次循环：

  • 现在 left = 7 和 right = 7。
  • while 循环的条件 left < right 不再满足，循环结束。

退出循环后：

  • 检查 left 位置的元素是否等于 left，即 records[7] 和 7，比较 8 和 7。
  • 因为 records[left] 不等于 left，直接返回 left 的值，即 7。

然而，根据代码逻辑，如果 left 位置的元素等于 left，我们应该返回 left + 1；否则，返回 left。在本例中，left 已经等于数组的长度，且 records[left] 实际上超出了正常的序列，因此正确结果应为 left 的值，即 7，这表明缺失的元素是 7。

因此，这段代码正确地找到了测试用例 [0, 1, 2, 3, 4, 5, 6, 8] 中缺失的元素，即 7。

🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀

以上，就是本期的全部内容啦，若有错误疏忽希望各位大佬及时指出💐

  制作不易，希望能对各位提供微小的帮助，可否留下你免费的赞呢🌸

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://xiahunao.cn/news/3223957.html

如若内容造成侵权/违法违规/事实不符，请联系瞎胡闹网进行投诉反馈，一经查实，立即删除！

相关文章

解决安卓tv 蓝牙遥控器配对后输入法弹不出来的问题

解决安卓tv 蓝牙遥控器配对后输入法弹不出来的问题

t972在蓝牙配对后，自带的LatinIME 输入法会出现弹不出来的现象。 经过分析，主要为蓝牙的kl 文件适配存在问题。解决如下： 1.新建 kl文件Vendor_2b54_Product_1600.kl 放到 /vendor/usr/keylayout/下 内容： #for bl remote add by jason 20240709 key 113 VOLUME_MUTE …
阅读更多...
来一场栈的大模拟（主要是单调栈）

来一场栈的大模拟（主要是单调栈）

一.栈模拟 二.单调栈求最大矩形面积 通常&#xff0c;直方图用于表示离散分布&#xff0c;例如&#xff0c;文本中字符的频率。 现在&#xff0c;请你计算在公共基线处对齐的直方图中最大矩形的面积。 图例右图显示了所描绘直方图的最大对齐矩形。 输入格式 输入包含几个测…
阅读更多...
Java内存区域与内存溢出异常（补充）

Java内存区域与内存溢出异常（补充）

2.2.5 方法区 方法区(Method Area)与Java堆一样&#xff0c;是各个线程共享的内存区域&#xff0c;它用于存储已被虚拟机加载的类型信息、常量、静态变量、即时编译器编译后的代码缓存等数据。虽然《Java虚拟机规范》中把方法区描述为堆的一个逻辑部分&#xff0c;但是它却有一…
阅读更多...
【C++】开源：坐标转换和大地测量GeographicLib库配置使用

【C++】开源：坐标转换和大地测量GeographicLib库配置使用

&#x1f60f;★,:.☆(&#xffe3;▽&#xffe3;)/$:.★ &#x1f60f; 这篇文章主要介绍坐标转换和大地测量GeographicLib库配置使用。 无专精则不能成&#xff0c;无涉猎则不能通。——梁启超 欢迎来到我的博客&#xff0c;一起学习&#xff0c;共同进步。 喜欢的朋友可以关…
阅读更多...
“郑商企航”暑期社会实践赴美丽美艳直播基地开展调研

“郑商企航”暑期社会实践赴美丽美艳直播基地开展调研

马常旭文化传媒网讯&#xff08;记者张明辉报道&#xff09;导读&#xff1a;2024 年 7 月 3 日&#xff0c;商学院暑期社会实践团“郑商企航”在河南省郑州市新密市岳村镇美丽美艳直播基地&#xff0c;展开了一场意义非凡的考察活动&#xff0c;团队成员深度调研了直播基地的产…
阅读更多...
关于string的‘\0‘与string，vector构造特点加部分特别知识点的讨论

关于string的‘\0‘与string，vector构造特点加部分特别知识点的讨论

目录 前言&#xff1a; 问题一&#xff1a;关于string的\0问题讨论 问题二&#xff1a;C标准库中的string内存是分配在堆上面吗&#xff1f; 问题三&#xff1a;string与vector的capacity大小设计的特点 问题四&#xff1a;string的流提取问题 问题五&#xff1a;迭代器失…
阅读更多...
c++内存管理（上）

c++内存管理（上）

目录 引入 分析 说明 C语言中动态内存管理方式 C内存管理方式 new/delete操作内置类型 new和delete操作自定义类型 引入 我们先来看下面的一段代码和相关问题 int globalVar 1; static int staticGlobalVar 1; void Test() { static int staticVar 1; int localVar 1…
阅读更多...
MySQL：TABLE_SCHEMA及其应用

MySQL：TABLE_SCHEMA及其应用

MySQL TABLE_SCHEMA及其应用 - 文章信息 - Author: 李俊才 (jcLee95) Visit me at CSDN: https://jclee95.blog.csdn.netMy WebSite&#xff1a;http://thispage.tech/Email: 291148484163.com. Shenzhen ChinaAddress of this article:https://blog.csdn.net/qq_28550263/ar…
阅读更多...
（2）滑动窗口算法练习：无重复字符的最长子串

（2）滑动窗口算法练习：无重复字符的最长子串

无重复字符的最长子串 题目链接&#xff1a;3. 无重复字符的最长子串 - 力扣&#xff08;LeetCode&#xff09; 给定一个字符串 s &#xff0c;请你找出其中不含有重复字符的最长子串的长度。 输入: s "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是"a…
阅读更多...
二战架构师，拿下

二战架构师，拿下

前言 已经许久更新文章了&#xff0c;并不是因为我懒了&#xff0c;而是在备考系统架构师考试。个人感觉还是比较幸运的&#xff0c;低分飘过。现阶段任务也算完成了&#xff0c;记录一下感受。 什么是软考 软考&#xff0c;全称“计算机技术与软件专业技术资格&#xff08…
阅读更多...
快速入门，springboot知识点汇总

快速入门，springboot知识点汇总

学习 springboot 应该像学习一门编程语言一样&#xff0c;首先要熟练掌握常用的知识&#xff0c;而对于不常用的内容可以简单了解一下。先对整个框架和语言有一个大致的轮廓&#xff0c;然后再逐步补充细节。 前序: Spring Boot 通过简化配置和提供开箱即用的特性&#xff0c…
阅读更多...
解决了一个java Bug：Exception in thread “main“ java.lang.NullPointerException

解决了一个java Bug：Exception in thread “main“ java.lang.NullPointerException

写代码&#xff0c;遇到了个问题。 很纳闷&#xff0c;跟着人家写的代码。只能去查资料。 赶紧去找&#xff0c;自己的代码 逆天&#xff0c;赶紧改&#xff01; 成功了&#xff01;&#xff01;&#xff01;
阅读更多...
Msfvenom制作自己的专属Shell

Msfvenom制作自己的专属Shell

Msfvenom制作自己的专属Shell 如何通过Msfvenom来生成用户自己的专属Shell?有时候我们上传Shell到目标主机后&#xff0c;不仅我们自己可以连接&#xff0c;其他用户也可以连接&#xff0c;有时候会导致我们丢失该Shell&#xff0c;甚至该shell被用户发现并查杀。 实验环境 …
阅读更多...
昇思MindSpore25天学习Day19：CycleGAN图像风格迁移互换

昇思MindSpore25天学习Day19：CycleGAN图像风格迁移互换

(TOC)[CycleGAN图像风格迁移呼唤] 模型介绍 模型简介 CycleGAN(Cycle Generative Adversaial Network)即循环对抗生成网络&#xff0c;来自论文Link:Unpaired lmage-to-mage Translation using Cycle-Consistent AdvesairalNetworks该模型实现了—种在没有配对示例的情况下学…
阅读更多...
ByteMD富文本编辑器的vue3配置

ByteMD富文本编辑器的vue3配置

Git地址&#xff1a;GitHub - bytedance/bytemd: ByteMD v1 repository 控制面板输入 npm install bytemd/vue-next 下载成功后在src/main.ts中引用 import "bytemd/dist/index.css";引入后保存&#xff0c;下面是一些插件&#xff0c;比如说我用到gmf和hightLight&…
阅读更多...
如何压缩视频大小不改变画质，视频太大怎么压缩变小

如何压缩视频大小不改变画质，视频太大怎么压缩变小

在现代生活中&#xff0c;视频已经成为我们记录生活、分享快乐的重要工具。但随之而来的问题就是视频文件体积过大&#xff0c;不仅占用大量存储空间&#xff0c;还难以在社交平台上快速分享。别担心&#xff0c;下面我就来教大家几种简单有效的方法&#xff0c;让视频文件轻松…
阅读更多...
Qt 音频编程实战项目

Qt 音频编程实战项目

一Qt 音频基础知识 QT multimediaQMediaPlayer 类&#xff1a;媒体播放器&#xff0c;主要用于播放歌曲、网络收音 机等功能。QMediaPlaylist 类&#xff1a;专用于播放媒体内容的列表。 二 音频项目实战程序 //版本5.12.8 .proQT core gui QT multimedia greate…
阅读更多...
7.9数据结构

7.9数据结构

思维导图 作业 doubleloop.h #ifndef __DOUBLELOOP_H__ #define __DOUBLELOOP_H__#include <stdio.h> #include <stdlib.h>typedef int datatype; typedef struct node {union{int len;datatype data;};struct node *pri;//前驱指针struct node *next;//后继指针…
阅读更多...
vue3创建项目

vue3创建项目

1. 安装node.js&#xff0c;添加环境变量&#xff0c;确保cmd里能使用node命令以及npm命令&#xff1a;node --version npm --version 本人安装的版本如下&#xff1a; 2. 安装vue的脚手架 npm install -g vue/cli 3. 创建vue项目&#xff1a;1&#xff09;使用ui&#xff1…
阅读更多...
应急响应——勒索病毒

应急响应——勒索病毒

先上搜索引擎上搜 也可以用360来杀 但是都无法解密 可以解密的&#xff1a; linux
阅读更多...
最新文章

Copyright @ 2022~2023