MENU
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
Discuss this article in the forums
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
everyone’s been talking about.
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...