✦ScienexySCIENCE KNOWLEDGE LIBRARY
concept · INFO-CS-ADS-118

Binary Search

Binary search is an efficient searching algorithm that repeatedly divides a sorted search range into two halves and eliminates the half that cannot contain the target.

Explanation

Overview

Binary search is a divide-and-conquer searching algorithm that locates a target in an ordered collection by comparing the target with the middle element of the current search interval.

Purpose

Its purpose is to reduce the number of comparisons required to find an element in a sorted collection, especially when the collection contains many elements.

Working principle

Binary search maintains a search interval with a lower and an upper boundary. It examines the middle element and determines whether the target is equal to, smaller than, or greater than that element.

Key concepts

name: Core idea; description: The central focus of binary search is the capability described here: Binary search is an efficient searching algorithm that repeatedly divides a sorted search range into two halves and eliminates the half that cannot contain the target.; name: Problem context; description: Binary Search is relevant when a computational task requires the behavior or capability described by this topic.; name: Correct use; description: Before using binary search, check its assumptions, input requirements, expected output, and resource constraints.

Space complexity

O(1) auxiliary space for an iterative implementation. A recursive implementation uses O(log n) call-stack space in the worst case.

Example

Consider the sorted array [3, 8, 12, 17, 21, 26, 31, 39, 45] and target 26. The algorithm checks the middle value 21, moves to the right interval, checks 31, moves left, and then finds 26.

Pseudocode

BINARY_SEARCH(A, target):
low = 0
high = length(A) - 1
while low <= high:
mid = low + (high - low) // 2
if A[mid] == target:
return mid
else if A[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1

Example or application

Consider the sorted array [3, 8, 12, 17, 21, 26, 31, 39, 45] and target 26. The algorithm checks the middle value 21, moves to the right interval, checks 31, moves left, and then finds 26.

Definition

Binary search is a divide-and-conquer searching algorithm that locates a target in an ordered collection by comparing the target with the middle element of the current search interval.

Purpose

Its purpose is to reduce the number of comparisons required to find an element in a sorted collection, especially when the collection contains many elements.

Prerequisites

The collection must be sorted according to the same ordering used by the comparison operation. The algorithm is most efficient when elements can be accessed directly by index, as in an array.

Working Principle

Binary search maintains a search interval with a lower and an upper boundary. It examines the middle element and determines whether the target is equal to, smaller than, or greater than that element.

Algorithm Steps

  • Initialize the lower boundary to the first valid index.

  • Initialize the upper boundary to the last valid index.

  • Calculate the middle index of the current interval.

  • Compare the middle element with the target.

  • If they match, return the middle index.

  • If the target is smaller, continue searching the left half.

  • If the target is larger, continue searching the right half.

  • Repeat until the target is found or the search interval becomes empty.

Pseudocode

BINARY_SEARCH(A, target):
low = 0
high = length(A) - 1
while low <= high:
mid = low + (high - low) // 2
if A[mid] == target:
return mid
else if A[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1

Divide And Conquer

The algorithm divides the current search interval into smaller parts. Unlike algorithms that solve both parts, binary search continues with only the half that may contain the target.

Best Case

O(1) time when the middle element of the initial interval is the target.

Average Case

O(log n) time for a sorted array because the search interval is approximately halved after each comparison.

Worst Case

O(log n) time when the algorithm repeatedly narrows the interval before finding the target or determining that it is absent.

Space Complexity

O(1) auxiliary space for an iterative implementation. A recursive implementation uses O(log n) call-stack space in the worst case.

Midpoint Calculation

The expression low + (high - low) // 2 is commonly used to calculate the midpoint. It avoids the potential integer overflow associated with calculating (low + high) // 2 in fixed-width integer environments.

Search Interval

The standard inclusive-interval implementation maintains the invariant that any possible target must lie between low and high. When low becomes greater than high, the interval is empty.

Advantages

  • Much faster than linear search on large sorted arrays.

  • Requires only O(log n) comparisons in the worst case.

  • Can be implemented iteratively or recursively.

  • Useful for repeated lookups in data that remains sorted.

Limitations

  • Requires sorted data.

  • Sorting an unsorted collection introduces additional preparation cost.

  • Direct midpoint access is inefficient in linked lists.

  • Incorrect boundary updates can cause infinite loops or missed results.

Duplicate Handling

Ordinary binary search may return any matching occurrence when duplicates exist. Finding the first or last occurrence requires a modified version that continues searching after a match.

Practical Applications

  • Searching sorted arrays.

  • Looking up values in ordered indexes.

  • Finding insertion positions.

  • Searching numerical ranges.

  • Supporting efficient lookup operations in static datasets.

Implementation Considerations

The algorithm must use consistent comparison rules, correct interval boundaries, and a safe midpoint calculation. Empty arrays and targets outside the stored range should be handled correctly.

Key Takeaway

Binary search achieves logarithmic search time by eliminating half of the remaining interval after each comparison. Its efficiency depends on maintaining correctly sorted data.

Key Concepts

NameDescription

Core idea

The central focus of binary search is the capability described here: Binary search is an efficient searching algorithm that repeatedly divides a sorted search range into two halves and eliminates the half that cannot contain the target.

Problem context

Binary Search is relevant when a computational task requires the behavior or capability described by this topic.

Correct use

Before using binary search, check its assumptions, input requirements, expected output, and resource constraints.

Practice Questions

QuestionAnswer

What is the main purpose of binary search?

Binary search is an efficient searching algorithm that repeatedly divides a sorted search range into two halves and eliminates the half that cannot contain the target.

What should be checked before applying binary search?

For binary search, verify the stated inputs, assumptions, expected result, boundary cases, and time and memory constraints.

How can an implementation of binary search be validated?

Trace a representative binary search case manually, test its boundary conditions, and compare the result with the specification or a trusted baseline.

Learning Objectives

  • Explain the central idea and purpose of binary search.

  • Identify the assumptions, inputs, and conditions relevant to binary search.

  • Evaluate an application of binary search for correctness and practical resource requirements.

Sources and verification

Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.

  • Scienexy Computer Science Reference

Suggest a correction or source · More in Algorithms & Data Structures