[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:

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
    }
}