SAMSUNG 49-Inch Odyssey G9

Because earth is not flat

Description

This problem is about searching for a target value in a rotated sorted array. The array is initially sorted but has been rotated at some pivot unknown to you beforehand. The goal is to determine if the target value exists in the array.

Intuition

The array being rotated implies that it is split into two sorted subarrays. The key is to figure out in which part of the array the target might exist. By leveraging the properties of sorted arrays, you can eliminate half of the search space at each step, making the search more efficient.

Approach

1. Use a binary search to identify the target.
2. At each step, determine if the left or right half of the array is sorted.
3. Decide which half to continue searching based on the properties of the sorted half and the target value.
4. Adjust the search boundaries (start and end) until you find the target or exhaust the search space.

Complexity

Time Complexity:

O(log n) where n is the number of elements in the array. This is due to the binary search approach.

Space Complexity:

O(1) since no additional space is used beyond the input array.

Code

C++

class Solution {
public:
    bool search(vector<int>& nums, int target) {
        int start = 0;
        int end = nums.size() - 1;
        
        while (start <= end) {
            int mid = start + (end - start) / 2;
            if (nums[mid] == target) {
                return true;
            } else if (nums[start] < nums[mid]) {
                if (nums[start] <= target && target < nums[mid]) {
                    end = mid - 1;
                } else {
                    start = mid + 1;
                }
            } else if (nums[mid] < nums[start]) {
                if (nums[mid] < target && target <= nums[end]) {
                    start = mid + 1;
                } else {
                    end = mid - 1;
                }
            } else {
                start++;
            }
        }
        
        return false;
    }
};

Python

class Solution:
    def search(self, nums: List[int], target: int) -> bool:
        start, end = 0, len(nums) - 1
        
        while start <= end:
            mid = start + (end - start) // 2
            if nums[mid] == target:
                return True
            elif nums[start] < nums[mid]:
                if nums[start] <= target < nums[mid]:
                    end = mid - 1
                else:
                    start = mid + 1
            elif nums[mid] < nums[start]:
                if nums[mid] < target <= nums[end]:
                    start = mid + 1
                else:
                    end = mid - 1
            else:
                start += 1
        
        return False

Java

class Solution {
    public boolean search(int[] nums, int target) {
        int start = 0;
        int end = nums.length - 1;
        
        while (start <= end) {
            int mid = start + (end - start) / 2;
            if (nums[mid] == target) {
                return true;
            } else if (nums[start] < nums[mid]) {
                if (nums[start] <= target && target < nums[mid]) {
                    end = mid - 1;
                } else {
                    start = mid + 1;
                }
            } else if (nums[mid] < nums[start]) {
                if (nums[mid] < target && target <= nums[end]) {
                    start = mid + 1;
                } else {
                    end = mid - 1;
                }
            } else {
                start++;
            }
        }
        
        return false;
    }
}

JavaScript

var search = function (nums, target) {

    let start = 0;
    let end = nums.length - 1;
    while (start <= end) {
        let mid = start + Math.floor((end - start) / 2);
        if (target === nums[mid]) {
            return true;
        } else if (nums[start] < nums[mid]) {
            if (nums[start] <= target && nums[mid] > target) {
                
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        } else if (nums[mid] < nums[start]) {
            if (nums[end] >= target && nums[mid] < target) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        } else {
            start += 1;
        }
    }

    return false;
};