Binary Search Visualization

Efficient search in sorted arrays

Binary Search finds a specific element in a sorted array. Each comparison halves the search range, achieving O(log n) time complexity.

Range: 1-100
L
M
R
Mid Value -
=
Target -
Step:0 Range:[0, 0]
Click 'Start' to view animation

Algorithm Steps

  1. Initialize left pointer = 0, right pointer = n-1
  2. Calculate middle position mid = (left + right) / 2
  3. Compare arr[mid] with target:
  4. Equal: Found target, return mid
  5. arr[mid] > target: Target in left half, right = mid - 1
  6. arr[mid] < target: Target in right half, left = mid + 1
  7. Repeat 2-3 until left > right (not found)

Time and Space Complexity

Case Complexity Description
Best Case O(1) Target is exactly in the middle
Average/Worst O(log n) Search range halves each time
Space Complexity O(1) Only constant extra space

Why O(log n)? Range halves after each comparison, at most log₂(n) comparisons needed. For 1 million elements, only ~20 comparisons!

Applications

  • Finding elements in sorted arrays/lists
  • Database index queries (B-tree, B+tree)
  • Finding insertion positions (like bisect)
  • Finding roots of monotonic functions
  • 'Binary search the answer' in competitive programming
Sorted Search Database Index Binary Answer Numerical Methods

Implementation

def binary_search(arr, target):
    """二分查找 - 返回目标索引，未找到返回-1"""
    left, right = 0, len(arr) - 1
    
    while left <= right:
        mid = left + (right - left) // 2  # 防止溢出
        
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return -1


def lower_bound(arr, target):
    """查找第一个 >= target 的位置"""
    left, right = 0, len(arr)
    
    while left < right:
        mid = (left + right) // 2
        if arr[mid] < target:
            left = mid + 1
        else:
            right = mid
    
    return left


# 使用示例
arr = [1, 3, 5, 7, 9, 11, 13]
print(binary_search(arr, 7))   # 输出: 3
print(binary_search(arr, 6))   # 输出: -1
print(lower_bound(arr, 6))     # 输出: 3 (第一个>=6的位置)
public class BinarySearch {
    
    /**
     * 二分查找 - 返回目标索引，未找到返回-1
     */
    public static int binarySearch(int[] arr, int target) {
        int left = 0, right = arr.length - 1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;  // 防止溢出
            
            if (arr[mid] == target) {
                return mid;
            } else if (arr[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return -1;
    }
    
    /**
     * 查找第一个 >= target 的位置
     */
    public static int lowerBound(int[] arr, int target) {
        int left = 0, right = arr.length;
        
        while (left < right) {
            int mid = (left + right) / 2;
            if (arr[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        
        return left;
    }
    
    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9, 11, 13};
        System.out.println(binarySearch(arr, 7));  // 3
        System.out.println(binarySearch(arr, 6));  // -1
        System.out.println(lowerBound(arr, 6));   // 3
    }
}