小米面试算法题：搜索旋转排序数组

题目描述

假设有一个排序的按未知的旋转轴旋转的数组(比如， 0 1 2 4 5 6 7 可能成为 4 5 6 7 0 1 2)。给定一个目标值进行搜索，如果在数组中找到目标值返回数组中的索引位置，否则返回-1。你可以假设数组中不存在重复的元素。

样例

例1:

输入: [ 4, 5, 1, 2, 3] and target= 1,
输出: 2.

例2:

输入: [ 4, 5, 1, 2, 3] and target= 0,
输出: -1.

题解

应用二分法分类讨论。

注意一下分类的细节即可。

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

----------------------------
原文链接:https://blog.csdn.net/JiuZhang_ninechapter/article/details/104678863
作者：九章算法

程序猿的技术大观园：www.javathinker.net

[这个贴子最后由 flybird 在 2020-03-08 23:03:06 重新编辑]

Java精品书籍推荐