wpe41.gif (23084 bytes)CIS3355: Business Data Structures
Fall, 2008
 

What is a Binary Search and

What is an example of one?

A sequential list is the simplest way of traversing a list in order to find an element.  If a list is ordered, whether in ascending or descending order, we do not have to search every element on the list.  A binary search is performed on data that is sorted whether it is in the form of a tree, array, list or other structure.  A binary search is when we split a sorted list in half each time in order to reduce our list of potential candidates as quickly as possible.  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.

 

Consider the following example.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

5.  Element greater than the search number??

 

 

NO
NO

6.  Bottom = midpoint + 1 = 4 + 1 = 5

 

 

10
9
8
7
6
5
4
3
2
1

The new search list is:

The top remains unchanged

 

 

 

 

offset:
1

2
3
4
5
7
6
8
9
0

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

YES:  STOP  The search number was found

 

 

Now its time to answer some questions:

Question 1 

When you first perform a binary search you:

a)      Search starting from the lef

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 disadvantages of a binary search?

a)      Extensive Maintenance

b)      Must have an equal amount to locate the middle

c)  Programmatically more complex  

d)     a and c 

Answer

a and c) Extensive Maintenance and Programmatically more complex

Question 3 

What are some of the advantages of a binary search?

a)   Not as much maintenance involved

b)      Program not as complex

c)      Easy to find elements and good for longer lists 

d)  All of the above

Answer

c) Easy to find elements and good for longer lists

Question 4

Before doing a binary search, the information must be                             ?

a)  unsorted

b)  sorted

c) long

d)  None of of the above

Answer

b)  sorted

Question 5

True or False.  Sorted information can only be in ascending order.

Answer

False.  The sorted information can be in ascending or descending order.

Here are some excellent websites to look at:

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

http://www.cs.uregina.ca/Links/class-info/170/bsearch.html

http://www.cprogramming.com/tutorial.html

http://homepages.ius.edu/JDRUIN/html_pages/C++_examples.htm

http://msdn.microsoft.com/library/default.asp?url=/library/en-us/vccore/html/_core_Tips_for_Improving_Time.2d.Critical_Code.asp

 

 

 

 

 

 

 

 

 

Assume that we have the following array of sorted integers:

 

10
9
8
7
6
5
4
3
2
1

10
9
8
7
6
5
4
3
2
1

 

 

top = 9

 

8.  Find the midpoint = (bottom + top)/2 = (5 + 9)/2 = 7
7.  Is the bottom offset > top offset

 

 

 

offset:
1

2
3
4
5
7
6
8
9
0
10
9
8
7
6
5
4
3
2
1

NO

 

 

 

 

 

9.  Element at midpoint the search element??

bottom = 5

And we wished to find the integer 8.

 

 

top = 9
offsets
bottom = 0
1. Determine the bottom and top of the list
10
9
8
7
6
5
4
3
2
1

2.  Is the bottom offset > top offset??

NO
3.  Find the midpoint = (bottom +  top)/2 = (0 + 9)/2 = 4

                                                                                 

 

offset:
10
9
8
7
6
5
4
3
2
1
1

2
3
4
5
7
6
8
9
0
4.  Element at midpoint the search element??