当前位置:   article > 正文

【Java算法专场】二分查找(下)

【Java算法专场】二分查找(下)

目录

山脉数组的峰顶索引

算法分析 

算法步骤

算法代码

算法示例 

寻找峰值 

算法分析

算法步骤

算法代码

算法示例 

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

算法分析

算法步骤

算法代码

算法示例 

点名 

算法分析

算法步骤

算法代码

算法示例 


山脉数组的峰顶索引

算法分析 

本道题是要在一个先升后降的数组查找拐点,如果我们采用暴力搜索的话,时间复杂度为O(n),但题目要求我们设计时间复杂度为O(logn)的算法,我们不难看出这道题也是具有二段性的,那么我们就可以采用二分查找。

算法步骤

  1. 初始化:设置双指针left和right,初始化left为1,right为nums.length-2.(由于要找峰顶,那么数组的第一个数和倒数第一个数必然不是,那么我们可以从第二个数出发)。
  2. 比较查找:定义mid,mid=left+(right-left+1)/2(为什么要+1,是为了避免整数溢出),通过与前一个值比较,判断当前位置是处于上坡还是下坡。当nums[mid]>mid[mid-1],说明此时mid处于上坡,让left=mid,当nums[mid]<=nums[mid-1]说明此时在下坡,让right=mid-1.循环条件为:left<right(当left==right时,说明找到了峰顶)。
  3. 返回结果:当循环结束之后,此时返回left即可。

算法代码

  1. /**
  2. * 在山形数组中找到峰值的索引。
  3. * 山形数组是指一个数组,其中存在一个元素,它大于其前后的所有元素(即峰值),
  4. * 且该元素前后的元素递增或递减。
  5. *
  6. * @param arr 山形数组,不为空且长度至少为3。
  7. * @return 返回数组中峰值的索引。如果有多个峰值,返回任意一个即可。
  8. */
  9. public int peakIndexInMountainArray(int[] arr) {
  10. /* 初始化左右指针 */
  11. int left = 1, right = arr.length - 2;
  12. /* 使用二分查找法寻找峰值 */
  13. while (left < right) {
  14. /* 计算中间索引,避免整数溢出,并确保mid大于left */
  15. int mid = left + (right - left + 1) / 2;
  16. /* 如果中间元素大于其前一个元素,则峰值在mid或其右侧 */
  17. if (arr[mid] > arr[mid - 1]) {
  18. left = mid;
  19. } else {
  20. /* 否则,峰值在mid或其左侧 */
  21. right = mid - 1;
  22. }
  23. }
  24. /* 当左右指针相遇时,即找到峰值 */
  25. return left;
  26. }

时间复杂度为O(logn),n为数组的长度,每次循环都会干掉一半的数据。 

空间复杂度为O(1),只用了常数个变量。

算法示例 

以arr = [0,10,5,2]为例

第一步:初始化

left=1,right=2

第二步:查找峰顶

  1. mid=left+(right-left+1)/2=1+(2-1+1)/2=2,arr[mid]=5<arr[mid-1]=10,让right=mid-1=1.此时left=right=1,说明找到了峰顶。

第三步:返回结果

此时left=1,将left返回即可。  

寻找峰值 

算法分析

本道题与前面的题目类似,在数组中存在多个峰值,只需要找到其中一个峰值即可。若使用暴力解法,时间复杂度为O(n),我们可以使用二分查找,来降低复杂度,通过二分,能让时间复杂度达到O(logn).

算法步骤

  1. 初始化:定义双指针left和right,并初始化left为0,right为nums.length-1。
  2. 查找峰值:在eft和right之间进行循环。定义mid,mid=left+(right-left)/2,通过与后一个值比较,判断当前所处位置。当nums[mid]>nums[mid+1],说明此时在[left,mid]之间必然存在一个峰值,为什么能这样说?题目给我们说明了两边都是负无穷开始的,所以在[left,mid]中一定有峰值,让right=mid;当nums[mid]<=nums[mid+1]时,让left=mid+1即可,说明此时在[mid,left]中存在着峰值。循环条件为:left<right(当left和right相遇时,说明找到了峰值)
  3. 返回结果:将left返回即可。

算法代码

  1. /**
  2. * 寻找峰值元素的索引。
  3. * 峰值元素被定义为大于其邻居的元素。
  4. *
  5. * @param nums 整数数组,其中存在至少一个峰值元素
  6. * @return 返回峰值元素的索引
  7. */
  8. public int findPeakElement(int[] nums) {
  9. /* 初始化左右指针 */
  10. int left = 0;
  11. int right = nums.length - 1;
  12. /* 使用二分查找法寻找峰值 */
  13. while (left < right) {
  14. /* 计算中间索引,避免整数溢出 */
  15. int mid = left + (right - left) / 2;
  16. /* 如果中间元素大于其右侧元素,则峰值在左侧或就是中间元素 */
  17. if (nums[mid] > nums[mid + 1]) {
  18. right = mid;
  19. } else {
  20. /* 否则,峰值在右侧 */
  21. left = mid + 1;
  22. }
  23. }
  24. /* 当左右指针相遇时,即找到峰值 */
  25. return left;
  26. }

时间复杂度为O(logn),n为数组长度,在循环的过程中,每次都能排除掉一半的数据量。

空间复杂度为O(1),只用了常数个变量。 

算法示例 

 以nums=[1,2,1,3,5,6,4]

第一步:初始化

让left=0,right=6

第二步:查找峰值

  1. mid=left+(right-left)/2=0+(6-0)/2=3,  nums[mid]=3<nums[mid+1]=5,此时说明峰值可能在右区间,让left=mid+1=4

 2.mid=4+(6-4)/2=5,nums[mid]=6>nums[mid+1]=4,说明此时峰值在左区间,让right=mid。

3.mid=4+(5-4)/2=4,nums[mid]=5<nums[mid+1]=6,此时让left=mid+1,同时left和right相遇,说明此时找到了峰值.

 

第三步:返回结果

此时left=5,返回即可。 

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

 

算法分析

本道题是要在一个被旋转后的数组中找到最小的元素,采用暴力遍历的算法,时间复杂度能达到O(n),但题目要求我们设计O(logn)的算法,我们可以看得出本道题也是具有二段性的,可以看成两段升序的数组。

算法步骤

  1. 初始化:设置双指针left和right,初始化left=0,right=nums.length-1。
  2. 预处理:如果数组在旋转之后还是原来的顺序,那么我们可以直接返回第一个元素,所以可以判断一下数组末尾的元素是否大于数组起始位置的元素,若大于则直接返回,反之则继续进行下续操作。
  3. 查找最小值:定义mid,mid=left+(right-left)/2,我们可以与数组两边的数进行比较,这里采用数组最右侧的数。当nums[mid]>mid[right],说明此时最小值在右区间[mid,right]中,让left=mid+1,当nums[mid]<=nums[right]时,说明此时最小值在左区间[left,mid],让right=mid,为什么不是right=mid-1,因为mid此时的位置有可能是最小值。循环条件为:left<right(当left和right相遇时,说明找到了最小值)
  4. 返回结果:返回nums[left]或nums[right]即可。

算法代码

  1. /**
  2. * 在旋转后的有序数组中查找最小值。
  3. * 旋转有序数组是指原数组为非递减数组,将数组从某个位置分割成两部分,然后将两部分的顺序调换后形成的数组。
  4. * 例如,原数组[0,1,2,4,5,6,7]在数字4处旋转后变为[4,5,6,7,0,1,2]。
  5. * 此函数旨在在这种旋转后的数组中找到最小的数字。
  6. *
  7. * @param nums 旋转后的有序数组
  8. * @return 数组中的最小值
  9. */
  10. public int findMin(int[] nums) {
  11. int left = 0, right = nums.length - 1;
  12. // 如果数组的第一个元素小于最后一个元素,说明数组未旋转或旋转后的最小值就是第一个元素
  13. if (nums[left] < nums[right]) {
  14. return nums[left];
  15. }
  16. // 使用二分查找法寻找最小值
  17. while (left < right) {
  18. int mid = left + (right - left) / 2;
  19. // 如果中间位置的元素大于最右边的元素,说明最小值在mid右侧
  20. if (nums[mid] > nums[right]) {
  21. left = mid + 1;
  22. } else {
  23. // 否则,最小值在mid或其左侧
  24. right = mid;
  25. }
  26. }
  27. // 最终right指向最小值的位置
  28. return nums[right];
  29. }

时间复杂度为O(logn)

空间复杂度为O(1) 

算法示例 

 以nums = [4,5,6,7,0,1,2]为例

 第一步:初始化

left=0,right=6

第二步:预处理

此时nums[left]=4>nums[right]=7,继续进行下续操作

第三步:找最小值

  1. mid=left+(right-left)/2=0+(6-0)/2=3,nums[mid]=7>nums[right]=2,此时让left=mid+1=4

2.mid=4+(6-4)/2=5,nums[mid]=1<nums[right]=2,让right=mid=5

 

3.mid=4+(5-1)/2=4,nums[mid]=0<nums[right]=1,此时让right=mid,同时left和right相遇,结束循环。

第四步:返回结果

此时返回nums[left]=0即可。

点名 

 

算法分析

本道题是要在一个从0~n-1的数组中找缺失的数,我们可以采用哈希表来解决,但此时时空复杂度达到了O(n),这是一个有序的数组,我们可以采用二分查找来解决,使时间复杂度达到O(logn).我们可以发现,每个数组的下标和其元素是相同的,那么我们可以通过判断下标和元素的大小,来确定缺失值的位置。

算法步骤

  1. 初始化:设置双指针left和right,初始化left=0,right=nums.length-1
  2. 查找缺失数:定义mid,mid=left+(right-left)/2,当records[mid]==mid,说明此时在[left,mid]内的数是没有缺失的,让left=mid+1,当records[mid]!=mid,说明此时缺失值在[left,mid]中。循环条件为:left<right(当left和right相遇,说明可能找到了缺失值的位置)
  3. 返回结果:在返回left下标前,我们需要判断一下records[left]==left,若是相等,说明此时不缺值,返回left+1,反之,返回left即可。

算法代码

  1. /**
  2. * 记录出席情况的函数。
  3. * 通过数组记录每个人的出席情况,其中数组的索引代表人的编号,数组的值代表该人实际的出席编号。
  4. * 函数的目的是找到第一个未出席的人的编号。
  5. *
  6. * @param records 出席记录数组,数组的第i个元素表示第i个人的出席编号。
  7. * @return 返回第一个未出席的人的编号。如果所有人都出席了,则返回下一个应该出席的编号。
  8. */
  9. public int takeAttendance(int[] records) {
  10. /* 初始化左右指针 */
  11. int left = 0, right = records.length - 1;
  12. /* 使用二分查找法来寻找第一个未出席的人 */
  13. while (left < right) {
  14. /* 计算中间位置,避免整数溢出 */
  15. int mid = left + (right - left) / 2;
  16. /* 如果中间位置的人的出席编号等于其位置,则说明左边的人都出席了,调整左指针 */
  17. if (records[mid] == mid) {
  18. left = mid + 1;
  19. } else {
  20. /* 否则,说明中间位置的人未出席或者出席编号在左边,调整右指针 */
  21. right = mid;
  22. }
  23. }
  24. /* 检查最后一个人是否出席,如果出席则返回下一个出席编号,否则返回当前出席的最后一个编号 */
  25. return left == records[left] ? left + 1 : left;
  26. }

时间复杂度为O(logn),

空间复杂度为O(1) 

算法示例 

records = [0,1,2,3,5]

第一步:初始化

left=0,right=4

第二步:查找缺失值

  1. mid=left+(right-left)/2=0+(4-0)/2=2,records[mid]=2=mid,让left=mid+1

2.mid=3+(4-3)/2=3,records[mid]=3=mid,让left=mid+1,此时left=right,结束循环。

第三步:返回结果

此时判断records[left]是否等于left,但通过判断不是,所以这里直接返回left=4即可。

 


二分查找的算法专题就先到这里了~

若有不足,欢迎指正~

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/天景科技苑/article/detail/893175
推荐阅读
相关标签
  

闽ICP备14008679号