Animation: Binary Search Illustrating Divide and Conquer

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 then continued recursively to the right of the element.

the middle element is greater than the element to be found

The search is then 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 course of a binary search and shows the source code. To better understand the procedure the current code line is highlighted.

Additionally the source code was annotated showing which program line corresponds to which part of the divide and conquer strategy.

Screen Shot(s):

Start search at middle element

Second step of search

Element found; return its position

Classification

• Algorithms
• Searching Algorithms
• Algorithmic Strategies

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 Illustrating Divide and Conquer
Animation URL	http://www.animal.ahrgr.de/Anims/en/binarySearch1DAndC.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)	Guido Rößling
Date	1999-04-27
File Size size	2882 Byte
Number of Accesses:	9376
Added to DB by	Guido Rößling
Average Rating	6.1538(26 submitted ratings)
Language:	en
Number of Accesses:	9376

BibTeX bibliographic entry for citations:

@Misc{Rößling:1999,
   author = {Guido Rößling},
   title = {Binary Search Illustrating Divide and Conquer},
   howpublished = {WWW: \url{http://www.animal.ahrgr.de/Anims/en/binarySearch1DAndC.aml}},
 }