devbox
我家小花儿
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

代码随想录-day01-二分查找的相关题目推荐

作者：我家小花儿 | 2024-05-13 00:49:37

赞

踩

代码随想录-day01-二分查找的相关题目推荐

一、35.搜索插入位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

示例 1:

输入: nums = [1,3,5,6], target = 5
输出: 2

示例 2:

输入: nums = [1,3,5,6], target = 2
输出: 1

示例 3:

输入: nums = [1,3,5,6], target = 7
输出: 4

提示:

  • 1 <= nums.length <= 104
  • -104 <= nums[i] <= 104
  • nums 为 无重复元素 的 升序 排列数组
  • -104 <= target <= 104

这道题其实和示例题目差不多（示例题目在我的博客中可以找到，跳转链接），只是多了，最后如果数组中没有目标值，就要返回插入目标值的位置下标，但是你推算一下，其实左闭右闭的情况，最后的插入位置就是 left 的值，左闭右开的情况，最后的插入位置就是 right 的值

第一种方法（左闭右闭）：

  1. class Solution {
  2.    	public int searchInsert(int[] nums, int target) {
  3.  
  4. 		int left = 0;
  5. 		int right = nums.length - 1;
  6. 		
  7. 		while (left <= right) {
  8.  
  9. 			int middle = left + ((right - left) / 2);
  10. 			
  11. 			if (nums[middle] < target) {
  12. 				left = middle + 1;
  13. 			} else if (nums[middle] > target) {
  14. 				right = middle - 1;
  15. 			} else {
  16. 				return middle;
  17. 			}
  18. 		}
  19. 		
  20. 		return left;  // 因为左闭右闭，如果最后数组内没有目标值
  21.                       // 那么left就是在right的右边一个，因此最后如果要插入目标值，就是left
  22.     }
  23. }

第二种方法（左闭右开）：

  1. class Solution {
  2.    	public int searchInsert(int[] nums, int target) {
  3.  
  4. 		int left = 0;
  5. 		int right = nums.length;
  6. 		
  7. 		while (left < right) {
  8.  
  9. 			int middle = left + ((right - left) / 2);
  10. 			
  11. 			if (nums[middle] < target) {
  12. 				left = middle + 1;
  13. 			} else if (nums[middle] > target) {
  14. 				right = middle;
  15. 			} else {
  16. 				return middle;
  17. 			}
  18. 		}
  19.  
  20.         return left;  
  21.         // 经过推算，左闭右开的情况下，left，right，middle都是最终目标值插入的位置
  22.         // 因此返回left和right都可，虽然middle也是，但是middle需要再经过一次计算，因此还是left和right更好
  23. 		
  24. //		return right;
  25. 		
  26. //		return left + ((right - left) / 2);
  27.  
  28.     }
  29. }

二、34.在排序数组中查找元素的第一个和最后一个位置

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

示例 1：

输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]

示例 2：

输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]

示例 3：

输入：nums = [], target = 0
输出：[-1,-1]

提示：

  • 0 <= nums.length <= 105
  • -109 <= nums[i] <= 109
  • nums 是一个非递减数组
  • -109 <= target <= 109

这里是代码随想录里面的解法，但是我确实没咋看懂，if的判断条件，为什么这么写也不说，最后自己推了一遍，算是推明白了（但是其实还是不咋懂哈哈哈哈哈），不过，这里注意奥！！！！！我在leetcode往下翻题解的时候发现一位大神，那个思维确实厉害！！（唉，还是太菜了，大神解法在官方解法下边）

代码随想录解法：

  1. class Solution {
  2.     public int[] searchRange(int[] nums, int target) {
  3.  
  4. 		int leftBorder = getLeftBorder(nums, target);
  5. 		int rightBorder = getRightBorder(nums, target);
  6.  
  7. 		// 如果数组中没有目标值或者数组为空，则返回的左右边界是初始值，皆为-2
  8. 		if (leftBorder == -2 || rightBorder == -2) {
  9. 			return new int[] { -1, -1 };
  10. 		}
  11.  
  12. 		// 这里为什么是左减右要大于1
  13. 		// 因为左边界实际上是目标值序列的最左边-1，右边界是目标值序列最右边+1
  14. 		// 这也就是为什么下面左边界要+1，而右边界需要-1的原因
  15. 		// 因此即使目标序列的长度为1，右边界-左边界最小也是2
  16. 		if (rightBorder - leftBorder > 1) {
  17. 			return new int[] { leftBorder + 1, rightBorder - 1 };
  18. 		}
  19. 		
  20. 		// 目标值在数组范围中，但是数组中不存在目标值
  21. 		// 例如：数组{3,6,7},target为5，此时左右边界分别为0，1
  22. 		// 不符合上述任何情况，但是应该返回{-1, -1}
  23. 		return new int[] { -1, -1 };
  24.  
  25. 	}
  26.  
  27. 	public int getLeftBorder(int[] nums, int target) {
  28.  
  29. 		int left = 0;
  30. 		int right = nums.length - 1;
  31. 		int leftBorder = -2;
  32.  
  33. 		while (left <= right) {
  34. 			int middle = left + ((right - left) / 2);
  35.  
  36. 			// 为什么nums[middle] >= target作为判断条件
  37. 			// 当中间值大于等于目标值的时候，让right一直左移，直到right是左边界-1
  38. 			// 因为判断的时候如果和目标值相等，这时候你不确定right是左边界-1还是目标值序列中的其中一个
  39. 			// 因此要让right继续左移，直到right位置的值比目标值小，且left位置的值又比目标值大
  40. 			// 此时的right就是左边界-1
  41. 			if (nums[middle] >= target) {
  42. 				right = middle - 1;
  43. 				leftBorder = right;
  44. 			} else {
  45. 				left = middle + 1;
  46. 			}
  47. 		}
  48.  
  49. 		return leftBorder;
  50. 	}
  51.  
  52. 	public int getRightBorder(int[] nums, int target) {
  53.  
  54. 		int left = 0;
  55. 		int right = nums.length - 1;
  56. 		int rightBorder = -2;
  57.  
  58. 		while (left <= right) {
  59. 			int middle = left + ((right - left) / 2);
  60.  
  61. 			// 与左边界同理，在中间值大于目标值的时候，让left右移，一直到left是目标值的右边界+1
  62. 			// 所以最终leftBorder要-1才是最终的值
  63. 			if (nums[middle] > target) {
  64. 				right = middle - 1;
  65. 			} else {
  66. 				left = middle + 1;
  67. 				rightBorder = left;
  68. 			}
  69. 		}
  70.  
  71. 		return rightBorder;
  72. 	}
  73. }

我感觉这个大神解法真的非常好，简单易懂，我这种新手都能看明白，对新手真的太友好了！！！吃水不忘挖井人，感谢这位爱做梦的鱼大神！大家可以看看，新手一看都懂！

大神解法：

  1. class Solution {
  2.     public int[] searchRange(int[] nums, int target) {
  3.        
  4.         return new int[] { getfirst(nums, target), getlast(nums, target) };
  5.     
  6.     }
  7.  
  8.     public static int getfirst(int[] nums, int target) {
  9.  
  10.         int left = 0;
  11.         int right = nums.length - 1;
  12.         int first = -1;
  13.  
  14.         while (left <= right) {
  15.  
  16.             int middle = ((right - left) / 2) + left;
  17.  
  18.             if (nums[middle] == target) {
  19.                 // 这里注意！！！！！！
  20.                 // 一定要先赋值，这样最后得到的last就是我们要输出的边界
  21.                 first = middle;
  22.                 right = middle - 1;
  23.             } else if (nums[middle] > target) {
  24.                 right = middle - 1;
  25.             } else {
  26.                 left = middle + 1;
  27.             }
  28.         }
  29.  
  30.         return first;
  31.     }
  32.  
  33.     public static int getlast(int[] nums, int target) {
  34.  
  35.         int left = 0;
  36.         int right = nums.length - 1;
  37.         int last = -1;
  38.  
  39.         while (left <= right) {
  40.  
  41.             int middle = ((right - left) / 2) + left;
  42.  
  43.             if (nums[middle] == target) {
  44.                 // 这里注意！！！！！！
  45.                 // 一定要先赋值，这样最后得到的first就是我们要输出的边界
  46.                 last = middle;
  47.                 left = middle + 1;
  48.             } else if (nums[middle] > target) {
  49.                 right = middle - 1;
  50.             } else {
  51.                 left = middle + 1;
  52.             }
  53.         }
  54.  
  55.         return last;
  56.     }
  57. }

三、69.x的平方根

给你一个非负整数 x ，计算并返回 x 的 算术平方根 。

由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。

注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

示例 1：

输入：x = 4
输出：2

示例 2：

输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。

提示：

  • 0 <= x <= 231 - 1

这题其实思路很简单，感觉还不如上一题难，求算数平方根的向下取整的正数，java默认就是向下取整，所以这点不用管

那么就是从0开始到x/2之间进行二分，如果循环期间有middle满足middle*middle==x，那么middle就是x的算数平方根，不牵扯到小数部分

如果循环结束都没找到，那么此时left是比算数平方根大的那个最近的整数，而right是比算数平方根小的那个最近的整数，因此返回right或者left-1都可以

此外，x==1的情况要另外判断，这里肯定有人要问为什么0不用另外判断呢？下面就都给你解释：

x==0时：此时left定义为0，而right=x/2也是0， middle也是0，循环时会判断0*0==0，这样就会直接输出0；

x==1时：此时left定义还是0，而right=x/2也还是0，二分结束时，left==1，right==0，此时应该输出1，但是你输出right是0不对，left是1也不对

所以x==1需要另外判断但是x==0不需要

  1. class Solution {
  2. 	public int mySqrt(int x) {
  3.  
  4. 		if (x == 1) {
  5. 			return 1;
  6. 		}
  7. 		
  8. 		int left = 1;
  9. 		int right = x / 2;
  10. 		
  11. 		while (left <= right) {
  12. 			int middle = ((right - left) / 2) + left;
  13. 			
  14. 			if ((long)middle * middle < x) {
  15. 				left = middle + 1;
  16. 			} else if ((long)middle * middle > x) {
  17. 				right = middle - 1;
  18. 			} else {
  19. 				return middle;
  20. 			}
  21. 		}
  22. 		// return left - 1;
  23.         return right;
  24.     }
  25. }

四、367.有效的算数平方根

给你一个正整数 num 。如果 num 是一个完全平方数，则返回 true ，否则返回 false 。

完全平方数 是一个可以写成某个整数的平方的整数。换句话说，它可以写成某个整数和自身的乘积。

不能使用任何内置的库函数，如  sqrt 。

示例 1：

输入：num = 16
输出：true
解释：返回 true ，因为 4 * 4 = 16 且 4 是一个整数。

示例 2：

输入：num = 14
输出：false
解释：返回 false ，因为 3.742 * 3.742 = 14 但 3.742 不是一个整数。

提示：

  • 1 <= num <= 231 - 1

这题的思路也不难，上一题会了这一题肯定也会，判断是否是一个完全平方数，那直接在二分过程中判断middle*middle == num是否成立，成立就是true，循环结束还不成立就是false咯~

但是注意别忘了，1还是要另外判断

不判断的话left=0， right=1/2=0，middle=0， 0*0不会等于1，但是1又是完全平方数，所以0要另外判断

  1. class Solution {
  2.     public boolean isPerfectSquare(int num) {
  3.  
  4. 		if (num == 1) {
  5. 			return true;
  6. 		}
  7.  
  8. 		int left = 1;
  9. 		int right = num / 2;
  10.  
  11. 		while (left <= right) {
  12. 			int middle = left + ((right - left) / 2);
  13. 			if ((long) middle * middle == num) {
  14. 				return true;
  15. 			} else if ((long) middle * middle < num) {
  16. 				left = middle + 1;
  17. 			} else {
  18. 				right = middle - 1;
  19. 			}
  20. 		}
  21.  
  22. 		return false;
  23. 	}
  24. }

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

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号