# Binary Search

## Binary Search

FIND MEMBERS

EDIT
LOG OUT

COMPETE
DESIGN CHALLENGES

DEVELOPMENT CHALLENGES

DATA SCIENCE CHALLENGES

COMPETITIVE PROGRAMMING

LEARN
GETTING STARTED

DESIGN

DEVELOPMENT

DATA SCIENCE

COMPETITIVE PROGRAMMING

COMMUNITY
OVERVIEW

PROGRAMS

FORUMS

STATISTICS

EVENTS

BLOG

Binary Search
By lovro– TopCoder Member
Binary search is one of the fundamental algorithms in computer science. In order to explore it, we’ll first build up a
theoretical backbone, then use that to implement the algorithm properly and avoid those nasty off-by-one errors
Finding a value in a sorted sequence
In its simplest form, binary search is used to quickly find a value in a sorted sequence (consider a sequence an ordinary
array for now). We’ll call the sought value the target value for clarity. Binary search maintains a contiguous subsequence
of the starting sequence where the target value is surely located. This is called the search space. The search space is
initially the entire sequence. At each step, the algorithm compares the median value in the search space to the target
value. Based on the comparison and because the sequence is sorted, it can then eliminate half of the search space. By
doing this repeatedly, it will eventually be left with a search space consisting of a single element, the target value.
For example, consider the following sequence of integers sorted in ascending order and say we are looking for the
number 55:
0

5

13

19

22

41

55

68

72

81

98

We are interested in the location of the target value in the sequence so we will represent the search space as indices into
the sequence. Initially, the search space contains indices 1 through 11. Since the search space is really an interval, it
suffices to store just two numbers, the low and high indices. As described above, we now choose the median value, which
is...