CIS3355: Business Data Structures
Fall, 2008
 

What Is A Binary Search And What Is An Example Of One?

A binary search consists on dividing a search interval in two parts, comparing the element being search with the central element. If for some reason they are not the same it redefines the sides of the searched interval, all depending whether the element is more than or less than the element being searched.  The process concludes when the element being searched is found or when the size of the searched interval is zero.

What Did You Just Said? Explain?

 

Let’s start again.

A binary search can only be done in lists already ordered and sorted.

The MAXIMUM number of searches required is: log₂n (where n= the number of elements on the list).

The AVERAGE number of searches required is: (log₂n) – 1 for (n>30).

Consider these next points:

a) If the number being searched is equal to the midpoint,

MIDPOINT = (BOTTOM + TOP)/2,

       Then stop the process the number has been found.

b) If the number being searched is less than the midpoint, you discard the right side of the list and you repeat the process again with the left side of the list only.

c) If the number being searched is greater than the midpoint, you discard the left side of the list and repeat the process with just the right the side of the list only.

I Need An Example, I Don’t Get It!!!!

OK, OK!!   Let’s consider the next example:

Assume we are trying to find number 7 on the list,

1. Find the top and the bottom of the list,

Bottom = 0                                        Top = 8

2. Is the bottom > top?  Is 0 > 8 ? NO.

3. Now find the midpoint, remember MIDPOINT = (Bottom + Top) / 2

                                                                                  = (0+8)/2 = 4

Now,

                      Midpoint = 20

4. Is the number at the midpoint equal to the number searched? 20 = 7 ?? NO.

5. Is the number searched greater than the midpoint? Is 7 > 20 ?? NO.

6. Then, knowing that, you discard the right side of the list.

Now you have,

7. Again, find top and bottom.  Is bottom > top?? 0 > 3 ?? NO.

8. Find Midpoint. MIDPOINT = (Bottom + Top) / 2

                                                   = (0 + 3)/2=1

Now your new midpoint is,

9.      Is the number at the midpoint equal to the number searched? Is 7 = 7 ?? YES.

THEN,

THE SEARCHED NUMBER WAS FOUND.

Check If You Can Answer These Questions:

1. 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.

2. What are some of the advantages of a binary search?

a)      Good for longer lists.

b)      Not as difficult as sequential searching

c)      Not as much maintenance involved

Answer   a) Good for longer lists

More information to be found at:

http://www.cs.bristol.ac.uk/Teaching/Resources/COMS30119/slides/ds2/sld039.htm?o=8002

http://www.fredosaurus.com/notes-cpp/algorithms/searching/binarysearch.html

http://mathbits.com/MathBits/CompSci/Arrays/Binary.htm