DEV Community

Shahrouz Nikseresht
Shahrouz Nikseresht

Posted on

Day 80: Python Search in Rotated Sorted rArray - Final Challenge O(log n) Binary Search Mastery (LeetCode #33 Vibes)

#challenge #python #algorithms #datastructures

Welcome to the grand finale, Day 80 of the #80DaysOfChallenges journey! 🎉 We've made it to the end of this epic 80-day adventure, conquering everything from basics to advanced algorithms, and what a way to wrap it up. This last intermediate challenge adapts binary search to find a target in a rotated sorted array, identifying the sorted half and narrowing bounds, achieving O(log n) time even with rotation. It combines midpoint checks, sorted side detection, and targeted search, a must-have skill for handling modified sorted data in interviews and real-world scenarios. If you've followed along, congratulations – you're now equipped with a solid foundation! If you're polishing binary search variants or celebrating the challenge completion, this "Python search rotated array" script demonstrates a function that's robust, works for rotated or non-rotated cases, and perfect for extending to duplicates or finding rotation points.

💡 Key Takeaways from Day 80: Rotated Array Search Function

This final task features a function that modifies standard binary search to detect sorted halves and decide the search direction, returning the index or -1. It's a decision-tree binary pattern: analyze mid, choose side. We'll detail: function with left/right pointers, loop for midpoint and half analysis, and main with input and result.

1. Function Design: Pointer Initialization and Loop Condition

The search_rotated function takes nums and target, returns index:

def search_rotated(nums: list[int], target: int) -> int:
    """Return index of target in rotated sorted array, or -1 if not found."""
    left = 0
    right = len(nums) - 1
Enter fullscreen mode Exit fullscreen mode

Left at 0, right at end-1. Handles empty implicitly with loop.

2. Loop Processing: Mid Calculation and Sorted Half Logic

Core while performs adapted binary:

    while left <= right:
        mid = (left + right) // 2

        if nums[mid] == target:
            return mid

        # left half is sorted
        if nums[left] <= nums[mid]:
            if nums[left] <= target < nums[mid]:
                right = mid - 1          # target in left half
            else:
                left = mid + 1           # target in right half
        # right half is sorted
        else:
            if nums[mid] < target <= nums[right]:
                left = mid + 1           # target in right half
            else:
                right = mid - 1          # target in left half

    return -1
Enter fullscreen mode Exit fullscreen mode

Computes mid, returns if match. Checks left-mid sorted (nums[left] <= nums[mid]). If yes and target in range, search left; else right. Else right-mid sorted, similar. Detects rotation, focuses search. O(log n) time.

3. Main Interactive: Array and Target Input

Script reads rotated sorted nums and target:

raw = input("Enter rotated sorted numbers (space-separated): ").strip()
nums = list(map(int, raw.split()))

target = int(input("Enter target value: ").strip())

index = search_rotated(nums, target)
print(f"Target index: {index}")
Enter fullscreen mode Exit fullscreen mode

Parses ints, prompts target, shows index or -1. Simple finale.

🎯 Summary and Reflections

This rotated search adapts binary by analyzing sorted halves, a fitting end to our 80 days. It reinforced:

  • Half detection: nums[left] <= nums[mid] for left sorted.
  • Range choices: Target in sorted? Narrow there, else other.
  • Rotation robustness: Handles no rotation seamlessly.

Reflections: As we close this challenge, remember the growth from day 1. Duplicates variant harder (LeetCode #81). Thank you for joining – keep coding! 🚀

Advanced Alternatives: Recursive binary. Find pivot first. Your rotated tip? Share!

🚀 Next Steps and Resources

Day 80 concludes #80DaysOfChallenges! What's next? More algos? Stay tuned!

Top comments (0)