Solutions

1. Brute Force

O(n) time | O(1) space

Intuition

We can check every element one by one and return the index of the first one that is equal to the target.

Algorithm

Iterate through the loop from the first element to the last element with i index.
Return i if the element at i is equal to the target.
Return -1 when the loop finishes.

target = 0

0123456

4 ≠ 0

1 / 6

Code

def search(nums: list[int], target: int) -> int:
    for i in range(len(nums)):
        if nums[i] == target:
            return i
    return -1

/**
 * @param {number[]} nums
 * @param {number} target
 * @returns {number}
 */
var search = function (nums, target) {
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] === target) return i
  }
  return -1
}

class Solution {
    public int search(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == target) return i;
        }
        return -1;
    }
}

2. Binary Search

O(logn) time | O(1) space

Intuition

We can use the binary search technique starting from the middle element instead of checking every element.

As the array is rotated, one of the halves around the middle element is sorted.

We can tell if the target element is in this half only by looking at its two ends.

Algorithm

Create left and right integer variables with the start and end indexes of the array as initial values.
Iterate through the loop while left is less than or equal to right.
Create mid, the middle index between left and right, and return it if the element there is equal to the target.
If the element at left is less than or equal to the element at mid, the left half is the sorted one:
- Assign mid - 1 to right if the target is between the elements at left and mid, dropping the right half.
- Otherwise assign mid + 1 to left, dropping the left half.
Otherwise the right half is the sorted one:
- Assign mid + 1 to left if the target is between the elements at mid and right, dropping the left half.
- Otherwise assign mid - 1 to right, dropping the right half.
Return -1 when the loop finishes.

target = 0

mid

0123456

left right

7 ≠ 0, 0 is not between 4 and 7

1 / 4

Code

def search(nums: list[int], target: int) -> int:
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid
        if nums[left] <= nums[mid]:
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        elif nums[mid] < target <= nums[right]:
            left = mid + 1
        else:
            right = mid - 1
    return -1

/**
 * @param {number[]} nums
 * @param {number} target
 * @returns {number}
 */
var search = function (nums, target) {
  let left = 0
  let right = nums.length - 1
  while (left <= right) {
    const mid = Math.floor((left + right) / 2)
    if (nums[mid] === target) return mid
    if (nums[left] <= nums[mid]) {
      if (nums[left] <= target && target < nums[mid]) right = mid - 1
      else left = mid + 1
    } else if (nums[mid] < target && target <= nums[right]) {
      left = mid + 1
    } else {
      right = mid - 1
    }
  }
  return -1
}

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