Modified Binary Search Flashcards
(5 cards)
What is Modified Binary Search?
Adapts binary search for non-standard sorted arrays.
Use Case: Rotated arrays, finding boundaries.
Example: Search in Rotated Sorted Array.
What are the key steps in Modified Binary Search?
- Initialize left=0, right=n-1.
- Find mid, determine sorted half.
- Adjust search range based on target.
Explain steps for Search in Rotated Sorted Array aloud.
How does Modified Binary Search apply to Search in Rotated Sorted Array?
Find target in rotated sorted array. Identify sorted half, adjust search range.
Example: Search in Rotated Sorted Array.
What are the complexity and gotchas of Modified Binary Search?
Time: O(log n), Space: O(1).
Gotchas: No rotation, duplicates.
List edge cases for Search in Rotated Sorted Array aloud.
Code example of Modified Binary Search.
```python
from typing import List
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
else:
if nums[mid] < target <= nums[right]:
left = mid + 1
else:
right = mid - 1
return -1
~~~
Sketch rotated array on paper.