LeetCode | Search in Rotated Sorted Array
Suppose a sorted array is rotated at some pivot unknown to you beforehand.
(i.e.,
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. 最も基本的な考え方は自然に一つ一つ遍歴して、意外にもacceptだとは思わなかった.
tagヒント:binary search
(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. 最も基本的な考え方は自然に一つ一つ遍歴して、意外にもacceptだとは思わなかった.
tagヒント:binary search
// ， ， rotate A ， 。
// ， ( ) 。 [ ]-[ ]， rotate ：[ ]-[ ]。
// (pivot) ， pivot ， ( )， ( )。
// 、 ， ：m = (l + r) /2
// A[m] < A[r]： m-r
// A[m] >= A[r]： l-m
public class Solution {
public int search(int[] nums, int target) {
int index = -1;
int left = 0;
int right = nums.length - 1;
while(left <= right){
int middle = (left+right) / 2;
if(nums[middle] == target){ //
index = middle;
break;
}
if(nums[middle] < nums[right]){ // m-r
if(nums[middle]