LeetCode 33. Search in Rotated Sorted Array I

 https://leetcode.com/problems/search-in-rotated-sorted-array/

https://www.youtube.com/watch?v=5qGrJbHhqFs&list=PLgUwDviBIf0pMFMWuuvDNMAkoQFi-h0ZF&index=5 

Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.

You must write an algorithm with O(log n) runtime complexity.

 

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

Example 3:

Input: nums = [1], target = 0

Output: -1

 

Constraints:

• 1 <= nums.length <= 5000

• -104 <= nums[i] <= 104

• All values of nums are unique.

• nums is an ascending array that is possibly rotated.

• -104 <= target <= 104

package LeetCode.binarySearch;

public class LT33_SearchInRotatedSortedArray {

    public static void main(String[] args) {
        int[] arr = {7, 8, 9, 1, 2, 3, 4, 5, 6};

        int target = 0;

        int idx = search(arr, target);
        System.out.println(idx);

    }

    public static int search(int[] nums, int target) {
        // Time Complexity: O(log n)
        // Space Complexity: O(1)

        int low = 0, high = nums.length - 1;

        while (low <= high) {

            int mid = low + (high - low) / 2;

            if (nums[mid] == target)
                return mid;

                // LEFT HALF IS SORTED
            else if (nums[low] <= nums[mid]) {

                if (nums[low] <= target && target <= nums[mid])
                    // Target lies in the left half
                    high = mid - 1;
                else
                    // Target lies in the right half
                    low = mid + 1;
            } else {
                // RIGHT HALF IS SORTED
                if (nums[mid] <= target && target <= nums[high])
                    // Target lies in the right half
                    low = mid + 1;
                else
                    // Target lies in the left half
                    high = mid - 1;
            }
        }

        return -1; // Target not found
    }
}


    }

🔍 Summary

Case	Time Complexity	Space Complexity
Best	O(1)	O(1)
Average	O(log n)	O(1)
Worst	O(log n)	O(1)