Notes

Modified Binary Search Technique

Modified Binary Search techniques are variations of the traditional binary search algorithm that are adapted to solve specific problems or work on specialized data structures. The traditional binary search algorithm is used to find the position of a target value within a sorted array in (O(\log n)) time. Modified versions extend this principle to handle more complex scenarios.

Key Concepts

1. Binary Search: A divide-and-conquer algorithm that repeatedly divides the search interval in half.
2. Modification: Adjusting the standard binary search to handle variations in data or specific problem requirements.

Applications

1. Finding the First or Last Occurrence of an Element.
2. Searching in a Rotated Sorted Array.
3. Finding the Peak Element in an Array.
4. Finding the Square Root of a Number.
5. Searching in a Nearly Sorted Array.

1. Finding the First or Last Occurrence of an Element

Problem: Given a sorted array with duplicate elements, find the first or last occurrence of a target value.

Code:

def find_first_occurrence(arr, target):
    left, right = 0, len(arr) - 1
    result = -1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            result = mid
            right = mid - 1  # continue to search on the left side
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return result

def find_last_occurrence(arr, target):
    left, right = 0, len(arr) - 1
    result = -1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            result = mid
            left = mid + 1  # continue to search on the right side
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return result

# Example usage:
arr = [1, 2, 2, 2, 3, 4, 5]
target = 2
print(find_first_occurrence(arr, target))  # Output: 1
print(find_last_occurrence(arr, target))   # Output: 3

Explanation:

1. Initialization: Start with the left and right pointers at the ends of the array.
2. Midpoint Calculation: Calculate the midpoint of the current search interval.
3. Adjust Search Range: If the target is found, update the result and adjust the search range to continue looking for the first or last occurrence.
4. Result: Return the index of the first or last occurrence.

2. Searching in a Rotated Sorted Array

Problem: Given a rotated sorted array, find the index of a target value.

Code:

def search_rotated_sorted_array(nums, target):
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid
        if nums[left] <= nums[mid]:  # left half is sorted
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        else:  # right half is sorted
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1
    return -1

# Example usage:
nums = [4, 5, 6, 7, 0, 1, 2]
target = 0
print(search_rotated_sorted_array(nums, target))  # Output: 4

Explanation:

1. Initialization: Start with the left and right pointers at the ends of the array.
2. Midpoint Calculation: Calculate the midpoint of the current search interval.
3. Determine Sorted Half: Check which half of the array is sorted.
4. Adjust Search Range: Narrow down the search range to the half that might contain the target.
5. Result: Return the index of the target if found, otherwise return -1.

3. Finding the Peak Element in an Array

Problem: Given an array, find the index of a peak element. A peak element is greater than its neighbors.

Code:

def find_peak_element(nums):
    left, right = 0, len(nums) - 1
    while left < right:
        mid = (left + right) // 2
        if nums[mid] > nums[mid + 1]:
            right = mid
        else:
            left = mid + 1
    return left

# Example usage:
nums = [1, 2, 3, 1]
print(find_peak_element(nums))  # Output: 2 (index of peak element 3)

Explanation:

1. Initialization: Start with the left and right pointers at the ends of the array.
2. Midpoint Calculation: Calculate the midpoint of the current search interval.
3. Compare Midpoint with Neighbor: Compare the midpoint with its right neighbor to determine the direction of the peak.
4. Adjust Search Range: Move the search range towards the peak.
5. Result: Return the index of the peak element.

4. Finding the Square Root of a Number

Problem: Find the integer square root of a non-negative integer ( x ).

Code:

def my_sqrt(x):
    if x < 2:
        return x
    left, right = 2, x // 2
    while left <= right:
        mid = (left + right) // 2
        num = mid * mid
        if num == x:
            return mid
        elif num < x:
            left = mid + 1
        else:
            right = mid - 1
    return right

# Example usage:
x = 8
print(my_sqrt(x))  # Output: 2

Explanation:

1. Initialization: Start with the left pointer at 2 and the right pointer at ( x // 2 ).
2. Midpoint Calculation: Calculate the midpoint of the current search interval.
3. Square Comparison: Compare the square of the midpoint with ( x ).
4. Adjust Search Range: Narrow down the search range based on the comparison.
5. Result: Return the integer part of the square root.

5. Searching in a Nearly Sorted Array

Problem: Given a nearly sorted array (where each element may be misplaced by at most one position), find the index of a target value.

Code:

def search_nearly_sorted_array(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        if mid - 1 >= left and arr[mid - 1] == target:
            return mid - 1
        if mid + 1 <= right and arr[mid + 1] == target:
            return mid + 1
        if arr[mid] < target:
            left = mid + 2
        else:
            right = mid - 2
    return -1

# Example usage:
arr = [10, 3, 40, 20, 50, 80, 70]
target = 40
print(search_nearly_sorted_array(arr, target))  # Output: 2

Explanation:

1. Initialization: Start with the left and right pointers at the ends of the array.
2. Midpoint Calculation: Calculate the midpoint of the current search interval.
3. Check Neighboring Elements: Check the midpoint and its immediate neighbors.
4. Adjust Search Range: Narrow down the search range based on the comparison.
5. Result: Return the index of the target if found, otherwise return -1.

1. 1004. Max Consecutive Ones III

This problem is typically solved using the sliding window technique, not binary search. However, if you wanted to use binary search to determine the maximum window size, you could explore different window sizes and use a helper function to check the validity, but this would be less efficient than the sliding window method.

Problem:

Given a binary array nums and an integer k, find the maximum number of consecutive 1s in the array if you can flip at most k 0s.

Code:
This problem doesn't naturally lend itself to a binary search solution in the traditional sense. Instead, the optimal approach is the sliding window method:

def longestOnes(nums: List[int], k: int) -> int:
    left = 0
    max_length = 0
    zeros_count = 0

    for right in range(len(nums)):
        if nums[right] == 0:
            zeros_count += 1

        while zeros_count > k:
            if nums[left] == 0:
                zeros_count -= 1
            left += 1

        max_length = max(max_length, right - left + 1)

    return max_length

Explanation:

• We expand the window size until we exceed the number of 0s that can be flipped, and then we start shrinking the window from the left side.
• This problem is best solved using the sliding window technique, and binary search is not a natural fit here.

33. Search in Rotated Sorted Array

Problem:
Given a rotated sorted array and a target value, find the index of the target. If not found, return -1.

Code:

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]:  # Left half is sorted
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        else:  # Right half is sorted
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1

    return -1

Explanation:

• We use binary search to identify which half of the array is sorted.
• Depending on whether the target lies within the sorted half, we adjust our search range.

34. Find First and Last Position of Element in Sorted Array

Problem:
Given a sorted array of integers nums and a target value, find the starting and ending position of the target.

Code:

def searchRange(nums: List[int], target: int) -> List[int]:
    def findLeft():
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        return left

    def findRight():
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] <= target:
                left = mid + 1
            else:
                right = mid - 1
        return right

    left_index = findLeft()
    right_index = findRight()

    if left_index <= right_index:
        return [left_index, right_index]
    return [-1, -1]

Explanation:

• Two binary searches are conducted: one for the first occurrence of the target (findLeft), and one for the last occurrence (findRight).
• This ensures both the start and end positions of the target are found efficiently.

69. Sqrt(x)

Problem:
Given a non-negative integer x, compute and return the square root of x. Since the return type is an integer, only the integer part of the result is returned.

Code:

def mySqrt(x: int) -> int:
    left, right = 0, x

    while left <= right:
        mid = (left + right) // 2
        if mid * mid == x:
            return mid
        elif mid * mid < x:
            left = mid + 1
        else:
            right = mid - 1

    return right

Explanation:

• The binary search finds the integer square root by narrowing down the possible values.
• If mid * mid is too small, the left boundary is adjusted; if too large, the right boundary is adjusted.

162. Find Peak Element

Problem:
A peak element is an element that is greater than its neighbors. Given an array of integers, find a peak element and return its index.

Code:

def findPeakElement(nums: List[int]) -> int:
    left, right = 0, len(nums) - 1

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

        if nums[mid] > nums[mid + 1]:
            right = mid
        else:
            left = mid + 1

    return left

Explanation:

• Binary search is used to find the peak by comparing the middle element with its neighbors.
• If the middle element is larger than the next, the peak is to the left; otherwise, it's to the right.

825. Friends Of Appropriate Ages

Problem:
Given an array representing the ages of a group of people, determine the number of friend requests made according to specific rules.

Code:
This problem does not naturally lend itself to binary search as the primary technique. Instead, a combination of sorting and two-pointer technique (which is sometimes referred to as a variation of binary search) is used to solve it efficiently.

def numFriendRequests(ages: List[int]) -> int:
    ages.sort()
    requests = 0

    for i in range(len(ages)):
        if ages[i] <= 14:
            continue

        left = bisect.bisect_left(ages, 0.5 * ages[i] + 7 + 1)
        right = bisect.bisect_right(ages, ages[i])

        requests += right - left - 1

    return requests

Explanation:

• The ages are sorted, and for each person, valid friend requests are counted by using binary search (bisect_left and bisect_right) to find the valid age range.
• This ensures that the number of friend requests is calculated efficiently.

Binary search is an essential technique for several of these problems, particularly when dealing with sorted arrays or when trying to minimize/maximize a certain condition within a range of values.

Summary

Modified binary search techniques adapt the basic binary search algorithm to solve a variety of problems more efficiently. By leveraging the divide-and-conquer strategy, these techniques can handle different data structures and problem constraints. Understanding and implementing these variations can significantly improve the performance of your algorithms for specific use cases.