> For the complete documentation index, see [llms.txt](https://frost.gitbook.io/iosbook/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://frost.gitbook.io/iosbook/leet-code/leetcode-solutions/untitled-4.md).

# \[LeetCode] 33. Search in Rotated Sorted Array

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(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.

Your algorithm's runtime complexity must be in the order of *O*(log *n*).

**Example 1:**

```
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4
```

**Example 2:**

```
Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1

```

**Analyse:**

​

**Solution:**

```swift
class Solution {
    //traget 1
    // 7 0 1 2 4 5 6
    // 4 5 6 7 0 1 2
    
    func search(_ nums: [Int], _ target: Int) -> Int {
    
        var startIndex = 0;
        var endIndex = nums.count - 1;
        
        while(startIndex <= endIndex) {
            
            let startValue = nums[startIndex];
            let middleIndex = startIndex + (endIndex - startIndex)/2;
            let middleValue = nums[middleIndex];
            let endValue = nums[endIndex];
            
            if(middleValue == target) {
                return middleIndex;
            }
            else if(middleValue >= startValue) {
                if(target >= startValue && target < middleValue) {
                   //  print("target >= startValue && target < middleIndex");
                     endIndex = middleIndex - 1;
                }
                else {
                     //print("target >= startValue && target < middleIndex 222");
                     startIndex = middleIndex + 1;
                }
            }
            else if(middleValue < startValue) {
                 //print("midValue <= target");
                
                if(target > middleValue && target <= endValue) {
                    // print("endValue: \(endValue) && target < middleIndex");
                    startIndex = middleIndex + 1;
                }
                else {
                    //  print("endValue: \(endValue) && target < middleIndex 222");
                    endIndex = middleIndex - 1;
                }
            }
        }

        return -1;
    }
}
```

\
**Solution 2:**

```
class Solution {
    func search(_ nums: [Int], _ target: Int) -> Int {
        let chars = Array(nums)
        var start = 0
        var end = chars.count - 1
        
        while(start <= end) {
            
            var middle = start + (end - start) / 2 //(end - start) / 2
            
            if(chars[middle] == target) {
                return middle
            } else if(chars[middle] >= chars[start]) {
              if(chars[start] <= target && target <= chars[middle]) {
                  end = middle  
              } else {
                  start = middle + 1
              }
                
            } else {
              if(chars[middle] <= target && target <= chars[end]) {
                  start = middle  
              } else {
                  end = middle - 1
              }
                
            }
        }
        
        return -1
    }
}
```