LeetCode 33 - Search in Rotated Sorted Array | May 22 POTD | Binary Search | O(log n) | Java

🔥 LeetCode 33 - Search in Rotated Sorted Array | May 22 POTD

📌 Problem:
Given an integer array nums sorted in ascending order with distinct
values, possibly left rotated at an unknown index k, and an integer
target — return the index of target if it is in nums, or -1 if not.
Algorithm must run in O(log n) time.

Example 1: nums = [4,5,6,7,0,1,2], target = 0 → Output: 4
Example 2: nums = [4,5,6,7,0,1,2], target = 3 → Output: -1
Example 3: nums = [1], target = 0 → Output: -1

💡 Approach: Modified Binary Search
Key Insight: Even though the array is rotated, at any point
ONE of the two halves is always sorted!

At each step check which half is sorted:

CASE 1 — Left half is sorted (arr[mid] is greater than or equal to arr[l]):
→ If target is greater than or equal to arr[l] AND target is less than arr[mid]
→ Search left half (r = mid - 1)
→ Else search right half (l = mid + 1)

CASE 2 — Right half is sorted:
→ If target is greater than arr[mid] AND target is less than or equal to arr[r]
→ Search right half (l = mid + 1)
→ Else search left half (r = mid - 1)

This guarantees O(log n) by always eliminating half the array!

⏱ Complexity:
- Time: O(log n) — classic binary search
- Space: O(1) — no extra space used

✅ Difficulty: Medium
📅 May 22, 2025 — Problem of the Day
🔗 Related: LC 153, LC 154 — already on this channel!

━━━━━━━━━━━━━━━━━━━━━━━
🔗 Problem Link:
https://leetcode.com/problems/search-in-rotated-sorted-array/

━━━━━━━━━━━━━━━━━━━━━━━

#leetcode #java #binarysearch #dsa #leetcodedaily #potd
#leetcodeMedium #competitiveprogramming #may22potd #leetcode33
#rotatedarray #searchrotatedarray #mustwatch #classicproblem

Видео LeetCode 33 - Search in Rotated Sorted Array | May 22 POTD | Binary Search | O(log n) | Java канала Vishant Sandilya