Skip to Main Content
Mastering Algorithms with C
book

Mastering Algorithms with C

by Kyle Loudon
August 1999
Intermediate to advanced content levelIntermediate to advanced
560 pages
18h 57m
English
O'Reilly Media, Inc.
Content preview from Mastering Algorithms with C

Description of Binary Search

Binary search is a technique for searching that works similarly to how we might systematically guess numbers in a guessing game. For example, suppose someone tells us to guess a number between and 99. The consistently best approach is to begin with 49, the number in the middle of and 99. If 49 is too high, we try 24, the number in the middle of the lower half of to 99 (0 to 48). Otherwise, if 49 is too low, we try 74, the number in the middle of the upper half of to 99 (50 to 99). We repeat this process for each narrowed range until we guess right.

Binary search begins with a set of data that is sorted. To start the search, we inspect the middle element of the sorted set. If the element is greater than the one we are looking for, we let the lower half of the set be the new set to search. Otherwise, if the element is less, we let the upper half be the new set. We repeat this process on each smaller set until we either locate the element we are looking for or cannot divide the set any further.

Binary search works with any type of data provided we can establish an ordering among the elements. It is a simple algorithm, but as you might suspect, its reliance on sorted data makes it inefficient for sets in which there are frequent insertions and deletions. This is because for each insertion or deletion, we must ensure that the set stays sorted for the search to work properly. Keeping a set sorted is expensive relative to searching it. Also, elements must be ...

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.
Start your free trial

You might also like

Introducing Algorithms in C: A Step by Step Guide to Algorithms in C

Introducing Algorithms in C: A Step by Step Guide to Algorithms in C

Luciano Manelli
Head First C

Head First C

David Griffiths, Dawn Griffiths

Publisher Resources

ISBN: 1565924533Supplemental ContentErrata Page