{ "@context": "https://schema.org", "@type": "Organization", "name": "Brainscape", "url": "https://www.brainscape.com/", "logo": "https://www.brainscape.com/pks/images/cms/public-views/shared/Brainscape-logo-c4e172b280b4616f7fda.svg", "sameAs": [ "https://www.facebook.com/Brainscape", "https://x.com/brainscape", "https://www.linkedin.com/company/brainscape", "https://www.instagram.com/brainscape/", "https://www.tiktok.com/@brainscapeu", "https://www.pinterest.com/brainscape/", "https://www.youtube.com/@BrainscapeNY" ], "contactPoint": { "@type": "ContactPoint", "telephone": "(929) 334-4005", "contactType": "customer service", "availableLanguage": ["English"] }, "founder": { "@type": "Person", "name": "Andrew Cohen" }, "description": "Brainscape’s spaced repetition system is proven to DOUBLE learning results! Find, make, and study flashcards online or in our mobile app. Serious learners only.", "address": { "@type": "PostalAddress", "streetAddress": "159 W 25th St, Ste 517", "addressLocality": "New York", "addressRegion": "NY", "postalCode": "10001", "addressCountry": "USA" } }

Modified Binary Search Flashcards

(5 cards)

1
Q

What is Modified Binary Search?

A

Adapts binary search for non-standard sorted arrays.

Use Case: Rotated arrays, finding boundaries.

Example: Search in Rotated Sorted Array.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

What are the key steps in Modified Binary Search?

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

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

A

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

Example: Search in Rotated Sorted Array.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

What are the complexity and gotchas of Modified Binary Search?

A

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

List edge cases for Search in Rotated Sorted Array aloud.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Code example of Modified Binary Search.

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly