給定一個以升序排列的整數陣列 nums（具有不同的值）。
在傳遞給你的函數之前，可能會在未知的軸心索引 k（1 <= k < nums.length）處對 nums 進行旋轉，
使得結果陣列為
[nums[k]、nums[k+1]、...、nums[n-1]、nums[0]、nums[1]、...、nums[k-1]]（索引從 0 開始）。
例如，[0,1,2,4,5,6,7] 可能會在軸心索引 3 處旋轉，變為 [4,5,6,7,0,1,2]。
給定可能旋轉後的陣列 nums 和一個整數目標 target，如果 target 存在於 nums 中，
則返回其索引；如果不存在，則返回 -1。
你必須使用 O(log n) 的時間複雜度編寫算法。
解題思路
由於原本的陣列是升序排列的，所以旋轉後一定至少有一邊是有序的。
以 [4,5,6,7,0,1,2] 為例，左邊 [4,5,6,7] 是有序的，右邊 [0,1,2] 也是有序的。
所以我們可以先判斷左邊或右邊是有序的，再判斷 target 是否在有序的那一邊。
如果是就繼續二分搜尋，如果不是就在另一邊繼續二分搜尋。
步驟:
1. 二分搜尋法
2. 由於陣列是旋轉過的，所以要先判斷左邊或右邊是有序的
3. 再判斷 target 是否在有序的那一邊。
如果是就繼續二分搜尋，如果不是就在另一邊繼續二分搜尋
Code
Java:
Runtime 0 ms(100%), Memory 41.5 MB(96.35%)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
class Solution {
public int search(int[] nums, int target) {
int leftFlag = 0;
int rightFlag = nums.length -1;
while(leftFlag <= rightFlag){
int midFlag = (leftFlag + rightFlag) / 2;
if (nums[midFlag] == target){
return midFlag;
}
if (nums[leftFlag] <= nums[midFlag]){
// if target is on left side
if(nums[leftFlag] <= target && target <= nums[midFlag]){
rightFlag = midFlag -1;
}else{
leftFlag = midFlag + 1;
}
}else{
if(nums[rightFlag] >= target && nums[midFlag] <= target){
leftFlag = midFlag + 1;
}else{
rightFlag = midFlag -1;
}
}
}
return -1;
}
}
|
Python3:
Runtime 62 ms(11.45%), Memory 16.7 MB(29.36%)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
class Solution:
def search(self, nums: List[int], target: int) -> int:
left_flag = 0
right_flag = len(nums) - 1
while left_flag <= right_flag:
mid_flag = (right_flag + left_flag) // 2
if nums[mid_flag] == target:
return mid_flag
if nums[left_flag] <= nums[mid_flag]:
if nums[left_flag] <= target and nums[mid_flag] >= target:
right_flag = mid_flag - 1
else:
left_flag = mid_flag + 1
else:
if nums[right_flag] >= target and nums[mid_flag] <= target:
left_flag = mid_flag + 1
else:
right_flag = mid_flag - 1
return -1
|
C#:
Runtime 84 ms(81.86%), Memory 39.3 MB(40.9%)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
public class Solution {
public int Search(int[] nums, int target) {
int LeftFlag = 0;
int RightFlag = nums.Length - 1;
while (LeftFlag <= RightFlag) {
int MidFlag = (LeftFlag + RightFlag) / 2;
if (nums[MidFlag] == target){
return MidFlag;
}
if (nums[LeftFlag] <= nums[MidFlag]){
if (nums[LeftFlag] <= target && target <= nums[MidFlag]){
RightFlag = MidFlag - 1;
}else{
LeftFlag = MidFlag + 1;
}
}else{
if (nums[MidFlag] <= target && target <= nums[RightFlag]){
LeftFlag = MidFlag + 1;
}else{
RightFlag = MidFlag - 1;
}
}
}
return -1;
}
}
|
Golang:
Runtime 4 ms(51.96%), Memory 2.5 MB(57.42%)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
func search(nums []int, target int) int {
leftFlag := 0
rightFlag := len(nums) - 1
for leftFlag <= rightFlag {
midFlag := (leftFlag + rightFlag) / 2
if nums[midFlag] == target {
return midFlag
}
if nums[leftFlag] <= nums[midFlag] {
if nums[leftFlag] <= target && target <= nums[midFlag] {
rightFlag = midFlag - 1
} else {
leftFlag = midFlag + 1
}
} else {
if nums[midFlag] <= target && target <= nums[rightFlag] {
leftFlag = midFlag + 1
} else {
rightFlag = midFlag - 1
}
}
}
return -1
}
|
C++:
Runtime 7 ms(32.87%), Memory 11.1 MB(31.74%)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
class Solution {
public:
int search(vector<int>& nums, int target) {
int intLeftFlag = 0;
int intRightFlag = nums.size() - 1;
while(intLeftFlag <= intRightFlag){
int intMidFlag = (intLeftFlag + intRightFlag) / 2;
if(nums[intMidFlag] == target){
return intMidFlag;
}
if(nums[intLeftFlag] <= nums[intMidFlag]){
if (nums[intLeftFlag] <= target && target <= nums[intMidFlag]){
intRightFlag = intMidFlag - 1;
}else{
intLeftFlag = intMidFlag + 1;
}
}else{
if (nums[intMidFlag] <= target && target <= nums[intRightFlag]){
intLeftFlag = intMidFlag + 1;
}
else{
intRightFlag = intMidFlag - 1;
}
}
}
return -1;
}
};
|
C:
Runtime 0 ms(100%), Memory 6 MB(64.74%)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
int search(int* nums, int numsSize, int target){
int leftFlag = 0;
int rightFlag = numsSize - 1;
while (leftFlag <= rightFlag) {
int midFlag = (leftFlag + rightFlag) / 2;
if (nums[midFlag] == target) {
return midFlag;
}
if (nums[leftFlag] <= nums[midFlag]) {
if (nums[leftFlag] <= target && target <= nums[midFlag]) {
rightFlag = midFlag - 1;
} else {
leftFlag = midFlag + 1;
}
} else {
if (nums[midFlag] <= target && target <= nums[rightFlag]) {
leftFlag = midFlag + 1;
} else {
rightFlag = midFlag - 1;
}
}
}
return -1;
}
|