Day 19 of 30 days Leetcode challenge - Search in Rotated Sorted Array

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

Solution

Take middle as pivot. One side is sorted, another side is not.
Find target in sorted side with binary search.
If target is not in the sorted side, repeat whole process for unsorted side.

class Solution {
    func search(_ nums: [Int], _ target: Int) -> Int {
        var l = 0, r = nums.count - 1
        while (l <= r) {
            
            if l == r { return nums[l] == target ? l : -1 }
            
            let m = (l + r) / 2
            if nums[m] == target { return m }
            
            //left partition is sorted
            if nums[l] <= nums[m] {
                if (nums[l] <= target) && (target <= nums[m]) {
                    r = m
                }else{
                    l = m + 1
                }
                continue
            }
            
            //right is sorted, check target inside or not
            if (nums[m + 1] <= target) && (target <= nums[r]) {
                l = m + 1
                continue
            }
        
            //left partion without middle
            r = m - 1
        }
        
        return -1
    }

}