leetcode刷题—二分查找

想成功先发疯，不顾一切向前冲

二分查找

No.1 （来个温柔的）

704.二分查找. - 力扣（LeetCode）

给定一个 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]之间。

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

为什么使用 (right - left) / 2 + left 公式？

使用公式 (right - left) / 2 + left 代替 (left + right) / 2 是为了避免 整数溢出。

• 在计算机中，整数有最大值。对于32位的 int 类型，这个最大值是 2,147,483,647。
• 如果 left 和 right 都很大（接近 Integer.MAX_VALUE），left + right 可能会超过这个最大值，导致整数溢出，计算错误。

No.2

34. - 力扣（LeetCode）

给你一个按照非递减顺序排列的整数数组 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]

class Solution {public int[] searchRange(int[] nums, int target) {int start = lowerBound(nums,target);if(start==nums.length||nums[start]!=target){return new int[]{-1,-1};}int end=lowerBound(nums,target+1)-1;return new int[]{start,end};      }private int lowerBound(int[] nums,int target){int left=0,right = nums.length-1;while(left<=right){int mid = (right-left)/2 +left;if(nums[mid]<target){left = mid+1;}else{right = mid-1;}}return left;}
}

设计解决方案

• 步骤1: 实现 lowerBound: lowerBound 函数应该返回数组中第一个大于或等于 target 的元素索引。
• 步骤2: 使用 lowerBound 确定范围:
  • 第一个 lowerBound 查找 target 的起始位置。
  • 第二个 lowerBound 查找 target + 1 的起始位置并减去 1，以获得 target 的结束位置。
• 边界条件处理: 检查如果 start 等于数组的长度或数组中位置 start 的元素不等于 target，返回 [-1, -1] 表示 target 不在数组中。

1. lowerBound 返回的是大于或等于 target 的第一个位置：

   • lowerBound(nums, target) 返回的是第一个不小于 target 的元素的索引。
   • 如果所有元素都小于 target，lowerBound 会返回数组长度 nums.length。
   • 如果返回的索引指向的值不等于 target，则说明数组中不存在 target。

2. 边界条件处理：

   • 如果 start == nums.length，说明数组中所有的元素都小于 target，即 target 不存在于数组中。
   • 如果 nums[start] != target，说明虽然我们找到了一个大于或等于 target 的位置，但是这个位置上的值并不是 target，即 target 不存在于数组中。

举个例子

假设数组 nums = [1, 3, 5, 7, 9] 和 target = 4，调用 lowerBound(nums, 4)：

• lowerBound 的返回值是 2（指向元素 5），因为 5 是第一个大于 4 的元素。
• 但是，nums[2] != 4，这意味着 4 并不在数组中。

因此，检查 if (start == nums.length || nums[start] != target) 这一行代码是必要的，用于验证找到的索引是否真的对应目标值 target。