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.

[2026] 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

아래 코드는 text를 사용한 구현 예제입니다. 코드를 직접 실행해보면서 동작을 확인해보세요.

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. 다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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: 다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

# 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

다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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: 다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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: 아래 코드는 python를 사용한 구현 예제입니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

# 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: 다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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: 다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

# 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: 아래 코드는 cpp를 사용한 구현 예제입니다. 필요한 모듈을 import하고. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

#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

다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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

다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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

다음은 python를 활용한 상세한 구현 코드입니다. 필요한 모듈을 import하고. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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

다음은 python를 활용한 상세한 구현 코드입니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

# ❌ 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

[2026] 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

이 글의 핵심

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