Modified Binary Search

Question 1

What is Modified Binary Search?

Answer 1

Adapts binary search for non-standard sorted arrays.

Use Case: Rotated arrays, finding boundaries.

Example: Search in Rotated Sorted Array.

Question 2

What are the key steps in Modified Binary Search?

Answer 2

1. Initialize left=0, right=n-1.
2. Find mid, determine sorted half.
3. Adjust search range based on target.

Explain steps for Search in Rotated Sorted Array aloud.

Question 3

How does Modified Binary Search apply to Search in Rotated Sorted Array?

Answer 3

Find target in rotated sorted array. Identify sorted half, adjust search range.

Example: Search in Rotated Sorted Array.

Question 4

What are the complexity and gotchas of Modified Binary Search?

Answer 4

Time: O(log n), Space: O(1).
Gotchas: No rotation, duplicates.

List edge cases for Search in Rotated Sorted Array aloud.

Question 5

Code example of Modified Binary Search.

Answer 5

```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.