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

2026년 3월 28일 · 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

자주 묻는 질문 (FAQ)

Q. 이 내용을 실무에서 언제 쓰나요?

A. Complete guide to binary search for coding interviews. Master basic binary search, lower bound, upper bound, and paramet… 실무에서는 위 본문의 예제와 선택 가이드를 참고해 적용하면 됩니다.

Q. 선행으로 읽으면 좋은 글은?

A. 각 글 하단의 이전 글 또는 관련 글 링크를 따라가면 순서대로 배울 수 있습니다. C++ 시리즈 목차에서 전체 흐름을 확인할 수 있습니다.

Q. 더 깊이 공부하려면?

A. cppreference와 해당 라이브러리 공식 문서를 참고하세요. 글 말미의 참고 자료 링크도 활용하면 좋습니다.

같이 보면 좋은 글 (내부 링크)

이 주제와 연결되는 다른 글입니다.

정렬 알고리즘 | 버블, 선택, 삽입 정렬 완벽 정리
BFS와 DFS | 그래프 탐색 알고리즘 완벽 정리
[BFS and DFS | Graph Traversal Algorithms Complete Guide](/en/blog/algorithm-series-10-bfs-dfs/

이 글에서 다루는 키워드 (관련 검색어)

Algorithm, Binary Search, Coding Interview, Sorting, Search 등으로 검색하시면 이 글이 도움이 됩니다.

이 글이 도움이 되셨나요?

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

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

Keyboard Shortcuts

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

자주 묻는 질문 (FAQ)

Q. 이 내용을 실무에서 언제 쓰나요?

Q. 선행으로 읽으면 좋은 글은?

Q. 더 깊이 공부하려면?

같이 보면 좋은 글 (내부 링크)

이 글에서 다루는 키워드 (관련 검색어)

이 글이 도움이 되셨나요?

Keyboard Shortcuts

이 글의 핵심

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

자주 묻는 질문 (FAQ)

Q. 이 내용을 실무에서 언제 쓰나요?

Q. 선행으로 읽으면 좋은 글은?

Q. 더 깊이 공부하려면?

같이 보면 좋은 글 (내부 링크)

이 글에서 다루는 키워드 (관련 검색어)

이 글이 도움이 되셨나요?