首页 > 代码库 > Search in Rotated Sorted Array I II

Search in Rotated Sorted Array I II

2024-07-05 22:54:30   227人阅读

Search in Rotated Sorted Array

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

用二分查找去做

 1 public int search(int[] A, int target) {
 2         int first = 0, last = A.length;
 3         while (first != last) {
 4             int mid = (first + last) / 2;
 5             if (A[mid] == target)
 6                 return mid;
 7             if (A[first] <= A[mid]) {
 8                 if (A[first] <= target && target < A[mid])
 9                     last = mid;
10                 else
11                     first = mid + 1;
12             } else {
13                 if (A[mid] < target && target <= A[last - 1])
14                     first = mid + 1;
15                 else
16                     last = mid;
17             }
18         }
19         return -1;
20     }
View Code

Search in Rotated Sorted Array II

Follow up for "Search in Rotated Sorted Array":
What if duplicates are allowed?

Would this affect the run-time complexity? How and why?

Write a function to determine if a given target is in the array.

允许重复，造成了如果A[m]>=A[l], 那么[l,m] 为递增序列的假设就不能成立了，比如[1,3,1,1,1]。

如果A[m]>=A[l] 不能确定递增，那就把它拆分成两个条件：
? 若A[m]>A[l]，则区间[l,m] 一定递增
? 若A[m]==A[l] 确定不了，那就l++，往下看一步即可。

因此复杂度从O(lgn)变成了O(n)。具体说明参见剑指offer上查找旋转数组的最小元素。

 1 public boolean search(int[] A, int target) {
 2         int first = 0, last = A.length;
 3         while (first != last) {
 4             int mid = (first + last) / 2;
 5             if (A[mid] == target)
 6                 return true;
 7             if (A[first] < A[mid]) {
 8                 if (A[first] <= target && target < A[mid])
 9                     last = mid;
10                 else
11                     first = mid + 1;
12             } else if (A[first] > A[mid]) {
13                 if (A[mid] < target && target <= A[last - 1])
14                     first = mid + 1;
15                 else
16                     last = mid;
17             } else {
18                 first++;
19             }
20         }
21         return false;
22     }
View Code

 


联系
我们