- Submitted By: Yash-Agrawal
- Date Submitted: 01/25/2016 6:11 AM
- Category: Technology
- Words: 3064
- Page: 13

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...