When to use binary search?

Use to find values in sorted arrays. Optimizes O(n) → O(log n).

Difference between lower bound and upper bound?

Lower bound finds first position ≥ x, upper bound finds first position > x.

What is parametric search?

Technique that converts optimization problems to decision problems solvable with binary search.

Binary Search | O(log n) Search Algorithm Complete Guide

2024년 8월 1일 · 16분 읽기 · 수정 2026년 3월 28일 Intermediate Tutorial

이 글의 핵심

Complete guide to binary search for coding interviews. Master basic binary search, lower bound, upper bound, and parametric search with principles and code examples.

Introduction

”Finding in Sorted Array = Binary Search”

Binary search finds values in sorted arrays in O(log n) time. Much faster than linear search O(n).

1. Binary Search Basics

Algorithm

Find 7 in [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
1. Check middle: arr[4] = 9 > 7 → left half
2. Check middle: arr[1] = 3 < 7 → right half
3. Check middle: arr[2] = 5 < 7 → right half
4. Check middle: arr[3] = 7 = 7 → found!

Python Implementation

Binary search cuts the array in half to reduce search space. Like finding a word in a dictionary - open to the middle, check if target is before or after, discard half.

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    
    while left <= right:
        mid = (left + right) // 2
        
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return -1
# Test
arr = [1, 3, 5, 7, 9, 11, 13, 15]
print(binary_search(arr, 7))   # 3
print(binary_search(arr, 10))  # -1
# Time complexity: O(log n)
# Search space halves each iteration
# n=1000 → max 10 comparisons
# n=1000000 → max 20 comparisons

Linear Search vs Binary Search:

# Linear search: O(n)
def linear_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1
# Worst case: check all elements (n times)
# Binary search: O(log n)
# Worst case: only log₂(n) checks
# 
# Performance comparison (n=1000000):
# Linear: 1000000 comparisons (worst)
# Binary: 20 comparisons (worst)
# → 50000x faster!

Recursive Implementation

def binary_search_recursive(arr, target, left, right):
    if left > right:
        return -1
    
    mid = (left + right) // 2
    
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search_recursive(arr, target, mid + 1, right)
    else:
        return binary_search_recursive(arr, target, left, mid - 1)
# Usage
arr = [1, 3, 5, 7, 9]
print(binary_search_recursive(arr, 7, 0, len(arr) - 1))  # 3

2. Lower Bound & Upper Bound

Lower Bound

Find first position ≥ x:

def lower_bound(arr, x):
    left, right = 0, len(arr)
    
    while left < right:
        mid = (left + right) // 2
        
        if arr[mid] < x:
            left = mid + 1
        else:
            right = mid
    
    return left
# Test
arr = [1, 2, 2, 2, 3, 4, 5]
print(lower_bound(arr, 2))  # 1 (first 2)
print(lower_bound(arr, 3))  # 4 (position of 3)
print(lower_bound(arr, 0))  # 0 (array start)
print(lower_bound(arr, 10))  # 7 (array end)

Lower Bound Usage:

# 1. Find first occurrence of duplicate
arr = [1, 2, 2, 2, 3, 4, 5]
first_2 = lower_bound(arr, 2)  # 1
# 2. Find insertion position (maintain sort)
arr = [1, 3, 5, 7, 9]
pos = lower_bound(arr, 6)  # 3
arr.insert(pos, 6)  # [1, 3, 5, 6, 7, 9]
# 3. Range query (count ≥ x)
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
count_gte_5 = len(arr) - lower_bound(arr, 5)  # 5

Upper Bound

Find first position > x:

def upper_bound(arr, x):
    left, right = 0, len(arr)
    
    while left < right:
        mid = (left + right) // 2
        
        if arr[mid] <= x:
            left = mid + 1
        else:
            right = mid
    
    return left
# Test
arr = [1, 2, 2, 2, 3, 4, 5]
print(upper_bound(arr, 2))  # 4 (after 2)
print(upper_bound(arr, 3))  # 5 (after 3)
print(upper_bound(arr, 5))  # 7 (array end)

Upper Bound Usage:

# 1. Count occurrences
def count_occurrences(arr, x):
    return upper_bound(arr, x) - lower_bound(arr, x)
arr = [1, 2, 2, 2, 3, 4, 5]
print(count_occurrences(arr, 2))  # 3
# 2. Range query (count ≤ x)
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
count_lte_5 = upper_bound(arr, 5)  # 5
# 3. Insert after duplicates
arr = [1, 2, 2, 2, 3]
pos = upper_bound(arr, 2)  # 4
arr.insert(pos, 2)  # [1, 2, 2, 2, 2, 3]

C++ STL Functions:

#include <algorithm>
#include <vector>
std::vector<int> arr = {1, 2, 2, 2, 3, 4, 5};
// Lower Bound: first position ≥ x
auto it1 = std::lower_bound(arr.begin(), arr.end(), 2);
// Upper Bound: first position > x
auto it2 = std::upper_bound(arr.begin(), arr.end(), 2);
// Count occurrences
int count = it2 - it1;  // 3

3. Parametric Search

Concept

Convert optimization problem → decision problem:

"What's the minimum?" → "Is k possible?" (binary search)

Example: Cutting Trees

def cut_trees(trees, h):
    """
    Total wood obtained when cutting at height h
    """
    return sum(max(0, tree - h) for tree in trees)
def find_max_height(trees, target):
    """
    Find maximum height that yields at least target wood
    """
    left, right = 0, max(trees)
    result = 0
    
    while left <= right:
        mid = (left + right) // 2
        
        if cut_trees(trees, mid) >= target:
            result = mid
            left = mid + 1  # Try higher
        else:
            right = mid - 1  # Try lower
    
    return result
# Test
trees = [20, 15, 10, 17]
target = 7
print(find_max_height(trees, target))  # 15
# Cut at 15: 5 + 0 + 0 + 2 = 7

Example: Minimum Speed to Arrive on Time

def min_speed_on_time(dist, hour):
    """
    Find minimum speed to complete all distances within hour
    """
    def can_arrive(speed):
        time = 0
        for i, d in enumerate(dist):
            if i < len(dist) - 1:
                time += (d + speed - 1) // speed  # Ceiling
            else:
                time += d / speed
        return time <= hour
    
    left, right = 1, 10**7
    result = -1
    
    while left <= right:
        mid = (left + right) // 2
        
        if can_arrive(mid):
            result = mid
            right = mid - 1  # Try slower
        else:
            left = mid + 1  # Need faster
    
    return result

4. Practical Tips

Using Python Built-ins

import bisect
arr = [1, 2, 3, 5, 6, 7]
# Lower bound
idx = bisect.bisect_left(arr, 4)
print(idx)  # 3
# Upper bound
idx = bisect.bisect_right(arr, 4)
print(idx)  # 3 (same for non-existent)
# Insert maintaining sort
bisect.insort(arr, 4)
print(arr)  # [1, 2, 3, 4, 5, 6, 7]

Common Mistakes

# ❌ Wrong: Overflow in C++
# mid = (left + right) / 2;  // Overflow!
# ✅ Correct: Safe method
# mid = left + (right - left) / 2;
# Python has no overflow concern
mid = (left + right) // 2
# ❌ Wrong: Off-by-one
# while left < right:  # vs left <= right
# return left vs return -1
# ✅ Correct: Consistent bounds
# [left, right] inclusive: left <= right
# [left, right) half-open: left < right

Summary

Key Points

Binary Search: O(log n) search in sorted arrays
Lower Bound: First position ≥ x
Upper Bound: First position > x
Parametric Search: Optimization → decision problem
Time Complexity: O(log n) - halves search space each step

When to Use

Problem Type	Approach	Reason
Find in sorted array	Binary Search	O(log n) vs O(n)
Count occurrences	Upper - Lower	O(log n)
Insert position	Lower/Upper Bound	Maintain sort
Optimization problem	Parametric Search	Convert to decision

Keywords

Binary Search, Algorithm, O(log n), Lower Bound, Upper Bound, Parametric Search, Sorted Array, Search Algorithm, Coding Interview, Time Complexity

Frequently Asked Questions (FAQ)

Q. When would I use this in practice?

A. Complete guide to binary search for coding interviews. Master basic binary search, lower bound, upper bound, and paramet…

Q. What should I read before this?

A. Follow the previous article or related articles links at the bottom of each post to learn in sequence.

Q. Where can I study this more deeply?

A. Check cppreference and the relevant library’s official documentation. The reference links at the end of the article are also worth using.

이 글이 도움이 되셨나요?

여러분의 피드백은 더 나은 콘텐츠를 만드는 데 도움이 됩니다

문제가 있거나 개선 제안이 있으시면 연락처로 알려주세요.

Binary Search | O(log n) Search Algorithm Complete Guide

이 글의 핵심

Introduction

”Finding in Sorted Array = Binary Search”

Binary search finds values in sorted arrays in O(log n) time. Much faster than linear search O(n).

1. Binary Search Basics

Algorithm

Python Implementation

Recursive Implementation

2. Lower Bound & Upper Bound

Lower Bound

Upper Bound

3. Parametric Search

Concept

Example: Cutting Trees

Example: Minimum Speed to Arrive on Time

4. Practical Tips

Using Python Built-ins

Common Mistakes

Summary

Key Points

When to Use

Recommended Problems

Beginner

Intermediate

Advanced

Keywords

Frequently Asked Questions (FAQ)

Q. When would I use this in practice?

Q. What should I read before this?

Q. Where can I study this more deeply?

이 글이 도움이 되셨나요?

이 글의 핵심

Introduction

”Finding in Sorted Array = Binary Search”

Binary search finds values in sorted arrays in O(log n) time. Much faster than linear search O(n).

1. Binary Search Basics

Algorithm

Python Implementation

Recursive Implementation

2. Lower Bound & Upper Bound

Lower Bound

Upper Bound

3. Parametric Search

Concept

Example: Cutting Trees

Example: Minimum Speed to Arrive on Time

4. Practical Tips

Using Python Built-ins

Common Mistakes

Summary

Key Points

When to Use

Recommended Problems

Beginner

Intermediate

Advanced

Related Posts

Keywords

Frequently Asked Questions (FAQ)

Q. When would I use this in practice?

Q. What should I read before this?

Q. Where can I study this more deeply?

Related Articles (Internal Links)

Keywords Covered in This Article (Related Search Terms)

이 글이 도움이 되셨나요?