大家好,我是开车的阿Q,自动驾驶的时代已经到来,没时间解释了,快和阿Q一起上车。作为自动驾驶系统工程师,必须要有最好的C++基础,让我们来一起刷题吧。
题目考察的知识点
这道题目主要考察二分查找算法的应用,以及如何在旋转数组中进行查找。
题目解答方法的文字分析
给定一个经过重新排列的牛棚数组和一个目标值 target
,我们需要在数组中查找目标值的下标。我们可以使用以下步骤来解决:
- 初始化两个指针
left
和right
分别指向数组的第一个和最后一个元素。 - 在每一轮二分查找中,计算中间元素的下标
mid
。 - 如果
nums[mid] == target
,直接返回mid
。 - 如果
nums[mid] <= nums[left]
,说明左半段是有序的。如果 target 在左半段的范围内,将 right 移动到 mid - 1。否则,将 left 移动到 mid + 1。 - 否则,右半段是有序的。如果 target 在右半段的范围内,将 left 移动到 mid + 1。否则,将 right 移动到 mid - 1。
- 循环直至
left
大于right
,表示没有找到目标值,返回 -1。
本题解析所用的编程语言
本题解析所用的编程语言是C++。
完整且正确的编程代码
class Solution { public: int search(vector<int>& nums, int target) { int left = 0, right = nums.size() - 1; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] == target) { return mid; } if (nums[mid] <= nums[left]) { // 当 nums[mid] 小于等于 nums[left] 时,说明左半段是有序的 if (target <= nums[left] && target > nums[mid]) { // 如果 target 在左半段的范围内,将 right 移动到 mid - 1 right = mid - 1; } else { // 否则,将 left 移动到 mid + 1 left = mid + 1; } } else { // 当 nums[mid] 大于 nums[left] 时,说明右半段是有序的 if (target < nums[mid] && target >= nums[right]) { // 如果 target 在右半段的范围内,将 left 移动到 mid + 1 left = mid + 1; } else { // 否则,将 right 移动到 mid - 1 right = mid - 1; } } } return -1; // 如果没有找到目标值,返回 -1 } };