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

2016-8-16 12:47| 发布者: zhangjf| 查看: 698| 评论: 0

摘要: 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 might become 4 5 6 7 0 1 2). You are given a target value to sear ...

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 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.

Example

For [4, 5, 1, 2, 3] and target=1, return 2.

For [4, 5, 1, 2, 3] and target=0, return -1.

Challenge

O(logN) time

Note

找中点：若起点小于中点，说明左半段没有旋转，否则说明右半段没有旋转。
在左右半段分别进行二分法的操作。

Solution

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

复制代码

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;
}
}

复制代码

收藏邀请

上一篇：[LintCode/LeetCode] Search Insert Position下一篇：Java Thread

		自动登录	找回密码
密码			立即注册

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

最新评论

相关分类