Binary search is a commonly used algorithmic pattern for efficiently searching for an element in a sorted array or performing other operations on a sorted data structure. It follows a divide-and-conquer approach by repeatedly dividing the search space in half. Here's an explanation of the binary search pattern along with example questions and solutions.

Binary Search Pattern:

1. Initialize pointers for the leftmost and rightmost elements of the search space.
2. Repeat until the search space is empty: a. Calculate the middle element of the search space. b. If the middle element matches the target, return the index or perform the required operation. c. If the middle element is less than the target, move the left pointer to the middle + 1. d. If the middle element is greater than the target, move the right pointer to the middle - 1.
3. Return a specific value or perform a required operation if the target is not found.

Example Question 1: Search in a Sorted Array Given a sorted array of integers and a target value, find the index of the target in the array. If the target is not found, return -1.

Solution:

def binary_search(nums, target):
    left = 0
    right = len(nums) - 1

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

        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return -1

Example Question 2: Search Insert Position Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be inserted in a sorted array.

Solution:

def search_insert(nums, target):
    left = 0
    right = len(nums) - 1

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

        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return left

Example Question 3: Square Root Given a non-negative integer x, compute and return the square root of x.

Solution:

def sqrt(x):
    if x < 2:
        return x

    left = 0
    right = x

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

        if mid * mid == x:
            return mid
        elif mid * mid < x:
            left = mid + 1
        else:
            right = mid

    return left - 1