力扣第三十三题——搜索旋转排序数组

内容介绍

   整数数组 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：

1. <strong>输入：</strong>nums = [4,5,6,7,0,1,2], target = 0
2. <strong>输出：</strong>4

复制代码

示例 2：

1. <strong>输入：</strong>nums = [4,5,6,7,0,1,2], target = 3
2. <strong>输出：</strong>-1

复制代码

示例 3：

1. <strong>输入：</strong>nums = [1], target = 0
2. <strong>输出：</strong>-1

复制代码

  提示：
  

• 1 <= nums.length <= 5000
  
• -104 <= nums <= 104
  
• nums 中的每个值都 独一无二
  
• 标题数据保证 nums 在预先未知的某个下标上进行了旋转
  
• -104 <= target <= 104
  

  完整代码

1. class Solution {
2.     public int search(int[] nums, int target) {
3.         int n = nums.length;
4.         if (n == 0) {
5.             return -1;
6.         }
7.         if (n == 1) {
8.             return nums[0] == target ? 0 : -1;
9.         }
10.         int l = 0, r = n - 1;
11.         while (l <= r) {
12.             int mid = (l + r) / 2;
13.             if (nums[mid] == target) {
14.                 return mid;
15.             }
16.             if (nums[0] <= nums[mid]) {
17.                 if (nums[0] <= target && target < nums[mid]) {
18.                     r = mid - 1;
19.                 } else {
20.                     l = mid + 1;
21.                 }
22.             } else {
23.                 if (nums[mid] < target && target <= nums[n - 1]) {
24.                     l = mid + 1;
25.                 } else {
26.                     r = mid - 1;
27.                 }
28.             }
29.         }
30.         return -1;
31.     }
32. }

复制代码

思绪详解

方法概述

search方法实现了一个改进的二分查找算法，适用于经过旋转的有序数组。旋转数组的特点是，数组的一部门是有序的，另一部门也是有序的，但是两部门之间的次序被打乱了。
思绪详解

• 边界情况处理：
  
  
  
  • 假如数组长度为0，直接返回-1，因为没有元素可以查找。
    
  • 假如数组长度为1，查抄该元素是否为目标值，假如是则返回索引0，否则返回-1。
    
  
  
• 初始化二分查找的左右指针：
  
  
  
  • l（左指针）初始化为0。
    
  • r（右指针）初始化为数组长度减1。
    
  
  
• 二分查找循环：
  
  
  
  • 当l小于等于r时，进行以下操纵：
    
    
    
    • 计算中央位置mid。
      
    • 假如nums[mid]等于目标值target，直接返回mid。
      
    
    
  
  
• 判定中央位置的元素与数组首元素的关系：
  
  
  
  • 假如nums[0]小于等于nums[mid]，说明左半部门是有序的：
    
    
    
    • 假如目标值target在nums[0]和nums[mid]之间，则将右指针r移动到mid - 1。
      
    • 否则，将左指针l移动到mid + 1。
      
    
    
  • 假如nums[0]大于nums[mid]，说明右半部门是有序的：
    
    
    
    • 假如目标值target在nums[mid]和nums[n - 1]之间，则将左指针l移动到mid + 1。
      
    • 否则，将右指针r移动到mid - 1。
      
    
    
  
  
• 循环竣事：
  
  
  
  • 假如循环竣事还没有找到目标值，说明目标值不在数组中，返回-1。
    
  
  

代码解释

以下是代码中关键步骤的解释：

1. public int search(int[] nums, int target) {
2.     int n = nums.length;
3.     if (n == 0) {
4.         return -1; // 数组为空，直接返回-1
5.     }
6.     if (n == 1) {
7.         return nums[0] == target ? 0 : -1; // 数组只有一个元素，检查是否为目标值
8.     }
9.     int l = 0, r = n - 1;
10.     while (l <= r) {
11.         int mid = (l + r) / 2; // 计算中间位置
12.         if (nums[mid] == target) {
13.             return mid; // 找到目标值，返回索引
14.         }
15.         if (nums[0] <= nums[mid]) {
16.             // 左半部分有序
17.             if (nums[0] <= target && target < nums[mid]) {
18.                 r = mid - 1; // 目标值在左半部分
19.             } else {
20.                 l = mid + 1; // 目标值在右半部分
21.             }
22.         } else {
23.             // 右半部分有序
24.             if (nums[mid] < target && target <= nums[n - 1]) {
25.                 l = mid + 1; // 目标值在右半部分
26.             } else {
27.                 r = mid - 1; // 目标值在左半部分
28.             }
29.         }
30.     }
31.     return -1; // 未找到目标值，返回-1
32. }

复制代码

知识点精粹

 
二分查找算法（Binary Search）

• 基本概念：一种在有序数组中查找特定元素的搜索算法，通过不断将搜索区间减半来提高搜索效率。
  
• 时间复杂度：O(log n)，此中n是数组的长度。
  

2. 循环数组的处理

• 旋转数组：一个有序数组在某些点上被旋转，使得数组的一部门有序，另一部门同样有序，但整体不再有序。
  
• 二分查找的适应：通过比较中央元素与数组首元素，确定哪部门是有序的，从而决定搜索方向。
  

3. 边界条件处理

• 空数组：假如数组为空，直接返回-1，因为没有元素可以查找。
  
• 单位素数组：假如数组只有一个元素，直接比较该元素与目标值。
  

4. 循环与递归的选择

• 循环实现：利用while循环进行二分查找，避免了递归大概带来的额外开销。
  

5. 中央位置的取值

• 防止溢出：利用(l + r) / 2计算中央位置，而非(l + r) >> 1，虽然后者在位运算上更高效，但在此场景下避免了整型溢出的风险。
  

6. 搜索区间的调整

• 左半部门有序：假如中央元素大于等于首元素，说明左半部门是有序的，根据目标值的位置调整搜索区间。
  
• 右半部门有序：假如中央元素小于首元素，说明右半部门是有序的，同样根据目标值的位置调整搜索区间。
  

7. 返回效果

• 找到目标值：假如中央元素等于目标值，返回中央位置的索引。
  
• 未找到目标值：假如循环竣事仍未找到目标值，返回-1。
  

8. 算法优化

• 避免重复比较：在每次循环中，仅比较一次中央元素与目标值，减少了不须要的比较次数。
  

通过以上知识点，我们可以看到，虽然代码实现的是二分查找，但针对旋转数组的特性进行了适当的调整，使得算法能够适应这种特别的有序数组。这些知识点对于明白和实现高效的搜索算法至关重要。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。