# 搜索旋轉排序的數組Leetcode解決方案

```array: [4,5,6,7,0,1,2]
target: 4```

```array: [4,5,6,7,0,1,2]
target: 3```
```-1
```

## 旋轉排序數組中的蠻力搜索方法

### 旋轉排序數組Leetcode解決方案中的搜索代碼

#### C ++代碼

```#include <bits/stdc++.h>
using namespace std;

int search(vector<int>& nums, int target) {
int n = nums.size();
for(int i=0;i<n;i++)
if(nums[i] == target)
return i;
return -1;
}

int main(){
vector<int> nums({4,5,6,7,0,1,2});
cout<<search(nums, 4);
}
```

#### Java代碼

```import java.util.*;
import java.lang.*;
import java.io.*;

class Main {
public static int search(int[] nums, int target) {
int n = nums.length;
for(int i=0;i<n;i++)
if(nums[i] == target)
return i;
return -1;
}

public static void main(String[] args){
int nums[] = {4,5,6,7,0,1,2};
System.out.println(search(nums, 4));
}
}```

### 複雜度分析

#### 空間複雜度

O（1），因為我們沒有關於每個元素的具體信息，並且使用了恆定數量的變量。 因此，空間複雜度是恆定的。

## 旋轉排序數組中的優化搜索方法

Sqrt（x）Leetcode解決方案

### 旋轉排序數組Leetcode解決方案中用於搜索的優化代碼

#### C ++代碼

```#include <bits/stdc++.h>
using namespace std;

int search(vector<int>& nums, int target) {
int n = nums.size();
int low = 0, high = n-1;
while(low<=high){
int mid = (low+high)/2;
// check if the current element is target
if(nums[mid] == target)
return mid;
// if the starting index of the search space has smaller element than current element
else if(nums[low]<=nums[mid]){
// if target lies in non-rotated search space (or subarray)
if(target >= nums[low] && target < nums[mid])
high = mid - 1;
else
low = mid + 1;
} else {
// if target lies in non-rotated subarray
if(target>nums[mid] && target<=nums[high])
low = mid + 1;
else
high = mid - 1;
}
}
// if you couldn't find the target element until now then it does not exists
return -1;
}
int main(){
vector<int> nums({4,5,6,7,0,1,2});
cout<<search(nums, 4);
}
```

#### Java代碼

```import java.util.*;
import java.lang.*;
import java.io.*;

class Main {
public static int search(int[] nums, int target) {
int n = nums.length;
int low = 0, high = n-1;
while(low<=high){
int mid = (low+high)/2;
// check if the current element is target
if(nums[mid] == target)
return mid;
// if the starting index of the search space has smaller element than current element
else if(nums[low]<=nums[mid]){
// if target lies in non-rotated search space (or subarray)
if(target >= nums[low] && target < nums[mid])
high = mid - 1;
else
low = mid + 1;
} else {
// if target lies in non-rotated subarray
if(target>nums[mid] && target<=nums[high])
low = mid + 1;
else
high = mid - 1;
}
}
// if you couldn't find the target element until now then it does not exists
return -1;
}

public static void main(String[] args){
int nums[] = {4,5,6,7,0,1,2};
System.out.println(search(nums, 4));
}
}```

### 複雜度分析

#### 時間複雜度

O（log N）， 因為我們已經使用二進制搜索來找到目標元素。 時間複雜度是對數的。

#### 空間複雜度

O（1）， 由於我們僅存儲了一定數量的元素，因此空間複雜度是恆定的。