Animation: Binary Search

Animation Systems Collection--Animations Collection

Description

Binary search is a procedure for searching an element in an array. The array has to be sorted in ascending order.

The basic idea is to compare the middle element of the array with the element to be found. The comparison can yield three results:

the middle element is the same as the element to be found

In this case the search is successful and the returns the index (field position) of the element to be found.

the middle element is smaller than the element to be found

The search is continued recursively to the right of the element.

the middle element is greater than the element to be found

The search is continued recursively to the left of the element.

With sorted data the binary search has a complexity of O(log n).

The animation demonstrates the process of binary searching and shows the source code. To better understand the procedure the current code line is highlighted.

Screen Shot(s):

Starting situation after determining middle element

Second comparison - Success!

Return the result - the index of the searched element

Classification

• Algorithms
• Searching Algorithms

Animation Rating

You can provide a rating for this animation. The rating is performed on a scale of 1 to 10, where 10 is the highest possible grade.

1(very bad) 2 3 4 5 6 7 8 9 10(very good)

File information

Title	Binary Search
Animation URL	http://www.animal.ahrgr.de/Anims/en/binarySearch1.aml
Animation Applet	Animal Applet
Animation System	Animal
Animation Type	dynamic full VCR
Supported OS(s)	Linux,MacOS,Windows 95,Windows 98,Windows ME,Windows NT,Windows 2000,Unix
Author(s)	Carsten Schwender
Date	1999-05-10
File Size size	2711 Byte
Number of Accesses:	12571
Added to DB by	Guido Rößling
Average Rating	4.1000(130 submitted ratings)
Language:	en
Number of Accesses:	12571

BibTeX bibliographic entry for citations:

@Misc{Schwender:1999,
   author = {Carsten Schwender},
   title = {Binary Search},
   howpublished = {WWW: \url{http://www.animal.ahrgr.de/Anims/en/binarySearch1.aml}},
 }