Binary Search

Binary search is a highly efficient searching algorithm used to find the position of a target value within a sorted array. This algorithm operates on the divide and conquer principle, which significantly reduces the time complexity compared to linear search methods.

Algorithm Workflow

1. Initial Setup: Binary search begins by identifying the middle element of the array. This is calculated using the formula:

   $$\text{mid} = \text{low} + \left(\frac{\text{high} - \text{low}}{2}\right)$$

   where low and high represent the indices of the start and end of the segment of the array being searched.

2. Comparison and Division:

   • If the middle element is equal to the target value, the search is complete.
   • If the target value is less than the middle element, the search continues in the left subarray (high is adjusted to mid - 1).
   • If the target value is greater than the middle element, the search continues in the right subarray (low is adjusted to mid + 1).

3. Recursive or Iterative Execution: This process is repeated either recursively or iteratively until the target value is found or the subarray reduces to zero (indicating that the target is not in the array).

Comparison of Interval Representations

• Closed Interval: Includes both boundary values; operations are symmetrical, reducing error chances.
• Left-Closed Right-Open: Does not include the upper boundary, changing how the interval emptiness is checked.

Complexity

Time Complexity

• Average and Worst Case: $O(\log n)$ - The search space is halved with each step, leading to a logarithmic time complexity.

Space Complexity

• Iterative Implementation: $O(1)$ - Uses constant space.
• Recursive Implementation: $O(\log n)$ - Due to the stack space used by recursive calls.

Advantages and Limitations

Advantages

• Efficiency: Significantly faster for large data sets compared to linear search.
• Space Conservation: Does not require extra space unlike some other search algorithms.

Limitations

• Requirement for Ordered Data: Only applicable to pre-sorted arrays.
• Unsuitability for Linked Lists: Inefficient for non-continuous data structures like linked lists.
• Overhead with Small Data: For very small datasets, the operational overhead of binary search can make it slower than linear search.

Implementation

def binary_search(nums: list[int], target: int) -> int:
	i, j = 0, len(nums) - 1
	while i <= j:
	    m = (i + j) // 2
	    if nums[m] < target:
	        i = m + 1
	    elif nums[m] > target:
	        j = m - 1
	    else:
	        return m
	return -1

Left Closed Right Open

def binary_search_lcro(nums: list[int], target: int) -> int:
	"""Binary search (left closed right open interval)"""
	i, j = 0, len(nums)
	# Loop until the search interval is empty (when i = j, it is empty)
	while i < j:
	    m = (i + j) // 2  # Calculate midpoint index m
	    if nums[m] < target:
	        i = m + 1  # This situation indicates that target is in the interval [m+1, j)
	    elif nums[m] > target:
	        j = m  # This situation indicates that target is in the interval [i, m)
	    else:
	        return m  # Found the target element, thus return its index
	return -1  # Did not find the target element, thus return -1