Animation: Unsuccessful 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 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 failed binary search and shows the source code. To better understand the procedure the current program line is highlighted.

Screen Shot(s):

Start with the middle element

Comparison with second chosen element

Comparison with third chosen element - too small, continue "right"

Failure of search - range invalid (r < l)

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	Unsuccessful Binary Search
Animation URL	http://www.animal.ahrgr.de/Anims/en/binarySearch2.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	3266 Byte
Number of Accesses:	5999
Added to DB by	Guido Rößling
Average Rating	5.8571(7 submitted ratings)
Language:	en
Number of Accesses:	5999

BibTeX bibliographic entry for citations:

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