[LintCode/LeetCode] Search in Rotated Sorted Array I & II

NO IMAGE

Search in Rotated Sorted Array

Problem

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

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

Search in Rotated Sorted Array II

Problem

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.

Note

只判斷有無,就容易了。

Solution

    public class Solution {
public boolean search(int[] A, int target) {
int start = 0, end = A.length-1;
while (start <= end) {
int mid = start (end-start)/2;
if (A[mid] == target || A[start] == target || A[end] == target) return true;
if (A[mid] < target) start = mid 1;
else end = mid-1;
}
return false;
}
}

還是可以用二分法優化

public class Solution {
public boolean search(int[] nums, int target) {
if (nums == null || nums.length == 0) return false;
int start = 0, end = nums.length-1;
while (start <= end) {
int mid = start (end-start)/2;
if (nums[mid] == target || nums[start] == target || nums[end] == target) return true;
if (nums[start] < nums[mid]) {
if (nums[start] <= target && target < nums[mid]) end = mid-1;
else start = mid 1;
}
else if (nums[start] > nums[mid]) {
if (nums[mid] < target && target <= nums[end]) start = mid 1;
else end = mid-1;
}
else {
if (nums[start] != target) start  ;
if (nums[end] != target) end--;
}
}
return false;
}
}