题目描述
假设有一个排序的按未知的旋转轴旋转的数组(比如,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 lineif (A[start] <= target && target <= A[mid]) {end = mid;} else {start = mid;}} else {// situation 2, green lineif (A[mid] <= target && target <= A[end]) {start = mid;} else {end = mid;}}} // whileif (A[start] == target) {return start;}if (A[end] == target) {return end;}return -1;}}