|
| 1 | +# 33.搜索旋转排序数组(中等)二分搜索 |
| 2 | +```text |
| 3 | +题目 假设按照升序排序的数组在预先未知的某个点上进行了旋转 |
| 4 | + (例如,数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2]) |
| 5 | + 搜索一个给定的目标值,如果数组中存在这个目标值,则返回它的索引,否则返回 -1; |
| 6 | + 你可以假设数组中不存在重复的元素。 |
| 7 | + 你的算法时间复杂度必须是 O(log n) 级别 |
| 8 | + 示例1 |
| 9 | + 输入 nums = [4,5,6,7,0,1,2], target = 0 |
| 10 | + 输出 4 |
| 11 | + 示例2 |
| 12 | + 输入 nums = [4,5,6,7,0,1,2], target = 3 |
| 13 | + 输出 -1 |
| 14 | +1.二分搜索 |
| 15 | + [1]思路 |
| 16 | + (1)先与旋转后的数组的首尾元素比较,若等于首或尾元素则直接返回,若在两者之间则不存在返回-1; |
| 17 | + (2)其余情况(即目标元素大于首元素或目标元素小于尾元素)进行二分搜索遍历; |
| 18 | + (3)取中间元素与目标元素进行比较,若相等则返回中间下标,否则根据条件确定所取区间; |
| 19 | + (4)当中间元素值大于等于首元素值,说明这个区间是升序的, |
| 20 | + 此时若目标值落在此升序区间则mid-1为新的右指针,否则mid+1为新的左指针; |
| 21 | + (5)当中间元素值小于首元素值,说明中间位置往右是升序的, |
| 22 | + 此时若目标值落在此升序区间则mid+1为新的左指针,否则mid-1为新的右指针; |
| 23 | + [2]实现 |
| 24 | + class Solution { |
| 25 | + public int search(int[] nums, int target) { |
| 26 | + int len = nums.length; |
| 27 | + if (len == 0) { |
| 28 | + return -1; |
| 29 | + } |
| 30 | + int i = 0, j = len - 1; |
| 31 | + if (target == nums[i]) { |
| 32 | + return i; |
| 33 | + } else if (target == nums[j]) { |
| 34 | + return j; |
| 35 | + } else if (target nums[j] && target nums[i]) { |
| 36 | + return -1; |
| 37 | + } |
| 38 | + while (i = j) { |
| 39 | + int mid = (i + j) 2; |
| 40 | + if (nums[mid] == target) { |
| 41 | + return mid; |
| 42 | + } |
| 43 | + if (nums[0] = nums[mid]) { |
| 44 | + if (nums[0] = target && target nums[mid]) { |
| 45 | + j = mid - 1; |
| 46 | + } else { |
| 47 | + i = mid + 1; |
| 48 | + } |
| 49 | + } else { |
| 50 | + if (target nums[mid] && nums[len - 1] = target) { |
| 51 | + i = mid + 1; |
| 52 | + } else { |
| 53 | + j = mid - 1; |
| 54 | + } |
| 55 | + } |
| 56 | + } |
| 57 | + return -1; |
| 58 | + } |
| 59 | + } |
| 60 | + [3]复杂度分析 |
| 61 | + (1)时间复杂度 O(logN),N为数组的长度 |
| 62 | + (2)空间复杂度 O(1) |
| 63 | +``` |
0 commit comments