33. Search in Rotated Sorted Array

Description

Given an array of integers nums and an integer target, return the index of the target if it exists in the array. If it does not exist, return -1. The search should be performed using a linear search algorithm.

Intuition

The problem requires us to find a target element in a list of integers. A straightforward approach to solve this is by using linear search, where we iterate through each element in the array and compare it with the target. If we find a match, we return the index; if we complete the iteration without finding a match, we return -1.

Approach

1. Initialize two pointers, left and right, to represent the start and end of the array, respectively.
2. Iterate through the array from the start using the left pointer.
3. For each element, compare it with the target. - If the element matches the target, return the current index (left). - If the element does not match, increment the left pointer.
4. If the iteration completes without finding the target, return -1.

Complexity

Time Complexity:

O(n), where n is the number of elements in the array. In the worst case, we may have to check all elements.

Space Complexity:

O(1), as no additional space is required other than a few integer variables.

Code

C++

class Solution {
public:
    int search(vector& nums, int target) {
        int left = 0;
        int right = nums.size() - 1;
        
        while (right >= left) {
            if (nums[left] == target) {
                return left;
            }
            left++;
        }
        
        return -1;
    }
};

Python

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left = 0
        right = len(nums) - 1

        while right >= left:
            if nums[left] == target:
                return left
            left += 1

        return -1

Java

class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;

        while (right >= left) {
            if (nums[left] == target) {
                return left;
            }
            left++;
        }

        return -1;
    }
}

JavaScript

var search = function (nums, target) {
    var right = nums.length - 1
    var left = 0;
    while (right >= left) {
        if (nums[left] === target) {
            return left
        }
        left++
    }
    return -1
};