Binary Search

overview

Remember these Terms

• Sorted array: Binary search works only when data is in ascending or descending order.
• Low/High: Index bounds of the current search range.
• Mid: Middle index computed as low + (high - low) // 2 to avoid overflow.
• Target: Value being searched.
• Invariant: Target, if present, lies within [low, high].
• Compare step: Move low or high based on target < or > arr[mid].
• Termination: Stop when found or low > high.
• Complexity: Time O(log n), space O(1).