What is a binary search and what is an
example of one?
A binary search is performed on data that is sorted whether it is in the form of a tree, array, list or other structure. It locates the middle entry of the array and the key value it is searching for. If it happens to be the middle element, then it completes its search, if not then it performs the search based on where the key value is greater or less than the middle element.
See example below of
a binary search.
To perform the binary search, consider the following array of characters:
|
Element |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
|
|
|
|
|
|
|
|
|
|
|
|
Character |
A |
D |
E |
F |
G |
M |
P |
S |
T |
Y |
Let's say we are searching for the character P:
- The
middle is located by adding the array subscript of the first character to
the subscript of the last character and dividing by two: (0 + 9)/2 =
4. The actual middle would be
between the elements 4 and 5. We
are using integer division which the element to be used is 4.
- Element
4 holds character G, which comes before character P. We know that P exists in that portion of
the array to the right of G. We
need to find the middle of the right portion of the array by using the
formula (5 + 9)/2 = 7.
- Element
7 holds the character S, which comes after the character P, so we need to
find the middle of the portion of the array to the right of character G,
but to the left of S using (5 + 6)/2 = 5
- Element
5 hold the character M, which comes before P, so we subdivide again (6 +
6)/2 = 6 and element 6 holds the character P.
Now let's see if you can answer some easy multiple choice questions.
Question 1
When you first perform a binary search you:
a) Search starting from the left
b) Search starting from the middle
c) Search starting from the right
d) Find the largest character and search from there
Answer
b) Search starting from the middle
Question 2
What are some of the draw backs of a binary search?
a) The information must be sorted
b) Must have an equal amount to locate the middle
c) It takes a long time to search all elements
d) a or c
Answer
a) The information must be sorted
Question 3
What are some of the advantages of a binary search?
a) Good for longer lists.
b) Program not as complex
c) Not as much maintenance involved
Answer
a) Good for longer lists
Question 4
Does it matter how the information is before doing a binary search?
Answer
Yes, the information must be sorted; it does not matter if it is in ascending or descending order
Here are some excellent websites to look at:
http://www.scg.uwaterloo.ca/~mwg/teaching/97-98/74.101/Notes/Class/part10/sld033.htm?o=8002
http://www.cs.bristol.ac.uk/Teaching/Resources/COMS30119/slides/ds2/sld039.htm?o=8002