33. 搜索旋转排序数组，34. 在排序数组中查找元素的第一个和最后一个位置 ，35. 搜索插入位置，每题做详细思路梳理，配套Python&Java双语代码， 2024.03.15 可通过leetcode所有测试用例。
目录
33. 搜索旋转排序数组
解题思路
完整代码
Python
Java
34. 在排序数组中查找元素的第一个和最后一个位置
解题思路
完整代码
Python
Java
35. 搜索插入位置
解题思路
完整代码
Python
Java
33. 搜索旋转排序数组
整数数组
nums按升序排列，数组中的值 互不相同 。在传递给函数之前，
nums在预先未知的某个下标k（0 <= k < nums.length）上进行了 旋转，使数组变为[nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如，[0,1,2,4,5,6,7]在下标3处经旋转后可能变为[4,5,6,7,0,1,2]。给你 旋转后 的数组
nums和一个整数target，如果nums中存在这个目标值target，则返回它的下标，否则返回-1。你必须设计一个时间复杂度为
O(log n)的算法解决此问题。示例 1：
输入：nums = [4,5,6,7,0,1,2], target = 0 输出：4示例 2：
输入：nums = [4,5,6,7,0,1,2], target = 3 输出：-1示例 3：
输入：nums = [1], target = 0 输出：-1
解题思路
为了在 O(log n) 的时间复杂度内解决这个问题，我们可以使用二分查找。由于数组在某个下标上进行了旋转，数组被分成了两部分，每部分都是有序的。我们的目标是确定 target 是否在有序的那部分中，如果不在，就在另一部分中查找。
具体步骤如下：
-
初始化：设置两个指针
left和right，分别指向数组的开始和结束。 -
二分查找：在
left <= right的条件下进行循环。- 计算中点
mid = (left + right) / 2。 - 如果
nums[mid]等于target，直接返回mid。 - 接下来判断
nums[mid]与nums[left]的关系，以确定哪部分是有序的。- 如果
nums[mid] >= nums[left]，说明左侧是有序的。- 如果
target在nums[left]和nums[mid]之间，我们应该在左侧查找，将right更新为mid - 1。 - 否则，在右侧查找，将
left更新为mid + 1。
- 如果
- 否则，右侧是有序的。
- 如果
target在nums[mid]和nums[right]之间，我们应该在右侧查找，将left更新为mid + 1。 - 否则，在左侧查找，将
right更新为mid - 1。
- 如果
- 如果
- 计算中点
-
返回结果：如果循环结束后还没有找到
target，返回-1。
完整代码
Python
class Solution:
def search(self, nums: List[int], target: int) -> int:
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return mid
# 判断左侧是否是有序的
if nums[left] <= nums[mid]:
# 如果目标值在左侧的有序区间内
if nums[left] <= target < nums[mid]:
right = mid - 1
else:
left = mid + 1
else:
# 右侧是有序的
if nums[mid] < target <= nums[right]:
left = mid + 1
else:
right = mid - 1
return -1Java
public class Solution {
public int search(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
}
if (nums[mid] >= nums[left]) {
// 左边是有序的
if (target >= nums[left] && target < nums[mid]) {
right = mid - 1; // target 在左边
} else {
left = mid + 1; // target 在右边
}
} else {
// 右边是有序的
if (target > nums[mid] && target <= nums[right]) {
left = mid + 1; // target 在右边
} else {
right = mid - 1; // target 在左边
}
}
}
return -1; // 没有找到 target
}
}
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]
解题思路
为了在 O(log n) 的时间复杂度内解决这个问题，我们可以使用二分查找的变种来分别找到目标值的开始位置和结束位置。这个方法包括两次二分查找：
- 查找开始位置：修改二分查找，使其在找到目标值时继续向左搜索，以找到目标值的最左侧索引。
- 查找结束位置：再次使用二分查找，但这次在找到目标值时继续向右搜索，以找到目标值的最右侧索引。
完整代码
Python
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
def binarySearchLeft(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return left
def binarySearchRight(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] <= target:
left = mid + 1
else:
right = mid - 1
return right
start = binarySearchLeft(nums, target)
end = binarySearchRight(nums, target)
if start <= end:
return [start, end]
else:
return [-1, -1]Java
public class Solution {
public int[] searchRange(int[] nums, int target) {
int[] result = new int[]{-1, -1};
result[0] = binarySearchLeft(nums, target);
result[1] = binarySearchRight(nums, target);
if (result[0] <= result[1]) {
return result;
}
return new int[]{-1, -1};
}
private int binarySearchLeft(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return left;
}
private int binarySearchRight(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] <= target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return right;
}
}
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
解题思路
-
初始化指针：设置两个指针
left和right，分别指向数组的开始和结束。 -
二分查找：当
left <= right时，计算中点mid = (left + right) / 2，并比较nums[mid]与target。- 如果
nums[mid]等于target，直接返回mid作为目标值的索引。 - 如果
nums[mid]小于target，则target应该在mid右侧，所以设置left = mid + 1。 - 如果
nums[mid]大于target，则target应该在mid左侧，所以设置right = mid - 1。
- 如果
-
返回插入位置：如果循环结束仍没有找到
target，那么target应该被插入在left指针当前的位置，此时left指针指向了数组中第一个大于target的元素位置，或者是数组的末尾。
完整代码
Python
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return leftJava
public class Solution {
public int searchInsert(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return left;
}
}
![python flask报错OSError: [WinError 10038] 在一个非套接字上尝试了一个操作。](https://img-blog.csdnimg.cn/direct/5bd21553e7c4449d96a267be09ae46aa.png)
