Anne Dawson: CSCI120A_LAB9_SP05.htm   

 

Last updated: Tuesday 15th March 2005, 5:07 PT

 

This document is subject to change without notice.

 

Please report any errors or omissions in this document:

adawson@coquitlamcollege.com

 

Special instructions:  For this assignment you may work in teams of 2, or alone.  This lab is due at the end of the lab session.

 

 

CSCI120A

 

Introduction to Computer Science and Programming

Spring 2005

Lab Assignment 9

Binary search of an ordered list

 

Step 1

 

Study the following program specification:

 

You are to write a program which performs a binary search of an ordered list of integers.  Your program reads in an ordered list of numbers from the supplied text file (data.txt) into a list.  The program then asks the user to enter a number. The program then performs a binary search for the number in the list (see algorithm and examples below). If the number is found, the program outputs the text: "Found at index: i",  where i is the index position of the integer in the list. If the number is not found, the program outputs the text: "Number not found".

 

Note: you do not type in the code of your program until Step 4.

 

Step 2

 

Study this algorithm for a binary search on an ordered list:

 

(X is the number to be found)

 

 

1.  Compare X to the middle value of the list.

2.  If X==Y (the middle element)

           we are done, number found.
    else If X < Y

           we continue our search confine the search to first half only.
    else If X > Y

           we continue our search confine the search to second half.

    else

           we are done, number not found.

 

3.  Repeat 1 and 2 until number found or number not found

 

Step 3

 

Study the pseudocode for a binary search on an ordered list:

 

Note: low and high are the low and high indexes of the list:

 

 

binarySearch(list, numbertofind, low, high)
 
    while low <= high
 
        mid = floor((low+high)/2)
 
        if list[mid] == numbertofind
 
            return mid
 
        else if numbertofind > list[mid]
 
            low  = mid+1
 
        else if numbertofind < list[mid]
 
            high = mid-1
        else
            return not found
 
    return not found

 

 

Step 4

 

Study the following two hand written examples.

 

Example 1: (Program outputs in bold text)

 

Assume that data.txt contains these 13 integers in ascending order:

 

       5   6   7  12  34  56  78  112  201  324   444   515   666

 

which have been read into a list:

 

Index: 0   1   2   3   4   5   6    7    8    9    10    11    12

       5   6   7  12  34  56  78  112  201  324   444   515   666

 

Note that low and high in the pseudocode above refer to the left and right indexes of the list. In the original list, low has a value of 0, high has a value of 12.

 

Enter the number to find:

 

12

 

Found at index: 3

 

 

 

How the program works:

 

Index: 0   1   2   3   4   5   6    7    8    9    10    11    12

       5   6   7  12  34  56  78  112  201  324   444   515   666

 

The high value is the list's length - 1, i.e. in this case is 12.

The low value at the start of the program is always 0.

 

Find the middle index by doing an integer division by 2 on (low + high):

(0+12)/2 is 6

 

Is 12 equal to the number at the middle index (index 6)?

 

No

 

Is the number > (greater than) the number at the middle index?

 

No

 

So search again on just the left half of the search list:

 

high is changed to mid -1, i.e. 6 - 1 = 5,

low remains unchanged at 0

 

check (low <= high) is true

 

New search:

 

Index: 0   1   2   3   4   5   6    7    8    9    10    11    12

       5   6   7  12  34  56  78  112  201  324   444   515   666

 

 

Find the middle index by doing an integer division by 2 on (low + high):

(0+5)/2 is 2

 

Index: 0   1   2   3   4   5   6    7    8    9    10    11    12

       5   6   7  12  34  56  78  112  201  324   444   515   666

 

 

Is 12 equal to the number at the middle index (index 2)?

 

No

 

Is the number > (greater than) the number at the middle index?

 

Yes

 

So make a new search with just the right half of the search list:

 

low is changed to mid +1, i.e. 2 + 1 = 3,

high remains unchanged at 5

 

Index: 0   1   2   3   4   5   6    7    8    9    10    11    12

       5   6   7  12  34  56  78  112  201  324   444   515   666

 

check (low <= high) is true

 

Find the middle index by doing an integer division by 2 on (low + high):

(3+5)/2 is 4

 

Index: 0   1   2   3   4   5   6    7    8    9    10    11    12

       5   6   7  12  34  56  78  112  201  324   444   515   666

 

 

Is 12 equal to the number at the middle index (index 4)?

 

No

 

Is the number > (greater than) the number at the middle index?

 

No

 

So search again on just the left half of the search list:

 

high is changed to mid -1, i.e. 4 - 1 = 3,

low remains unchanged at 3

 

check (low <= high) is true

 

New search:

 

Find the middle index by doing an integer division by 2 on (low + high):

(3+3)/2 is 3

 

Is 12 equal to the number at the middle index (index 3)?

 

Yes

 

 

Program output: "Found at index: 3"

 

 

 

Example 2:

 

Assume that data.txt contains these 13 integers in ascending order:

 

       5   6   7  12  34  56  78  112  201  324   444   515   666

 

which have been read into a list:

 

Index: 0   1   2   3   4   5   6    7    8    9    10    11    13

       5   6   7  12  34  56  78  112  201  324   444   515   666

 

Enter the number to find:

 

333

 

Number not found

 

How the program works:

 

Index: 0   1   2   3   4   5   6    7    8    9    10    11    12

       5   6   7  12  34  56  78  112  201  324   444   515   666

The high value is the list's length - 1, i.e. in this case is 12.

The low value at the start of the program is always 0.

 

Find the middle index by doing an integer division by 2 on (low + high):

(0+12)/2 is 6

 

Is 333 equal to the number at the middle index (index 6)?

 

No

 

Is the number > (greater than) the number at the middle index?

 

Yes

 

So search again on just the right half of the search list:

 

high remains unchanged at 12

low  is changed to mid +1, i.e. 6 + 1 = 7

 

 

check (low <= high) is true

 

New search:

 

Index: 0   1   2   3   4   5   6    7    8    9    10    11    12

       5   6   7  12  34  56  78  112  201  324   444   515   666

 

 

Find the middle index by doing an integer division by 2 on (low + high):

(7+12)/2 is 9

 

Index: 0   1   2   3   4   5   6    7    8    9    10    11    12

       5   6   7  12  34  56  78  112  201  324   444   515   666

 

 

Is 333 equal to the number at the middle index (index 9)?

 

No

 

Is the number > (greater than) the number at the middle index?

 

Yes

 

So make a new search with just the right half of the search list:

 

low is changed to mid +1, i.e. 9 + 1 = 10,

high remains unchanged at 12

 

Index: 0   1   2   3   4   5   6    7    8    9    10    11    12

       5   6   7  12  34  56  78  112  201  324   444   515   666

 

check (low <= high) is true

 

Find the middle index by doing an integer division by 2 on (low + high):

(10+12)/2 is 11

 

Index: 0   1   2   3   4   5   6    7    8    9    10    11    12

       5   6   7  12  34  56  78  112  201  324   444   515   666

 

 

 

Is 333 equal to the number at the middle index (index 11)?

 

No

 

Is the number > (greater than) the number at the middle index?

 

No

 

So search again on just the left half of the search list:

 

high is changed to mid -1, i.e. 11 - 1 = 10,

low remains unchanged at 10

 

Index: 0   1   2   3   4   5   6    7    8    9    10    11    12

       5   6   7  12  34  56  78  112  201  324   444   515   666

 

check (low <= high) is true

 

New search:

 

Find the middle index by doing an integer division by 2 on (low + high):

(10+10)/2 is 10

 

Index: 0   1   2   3   4   5   6    7    8    9    10    11    12

       5   6   7  12  34  56  78  112  201  324   444   515   666

 

 

Is 333 equal to the number at the middle index (index 10)?

 

No

 

Is the number > (greater than) the number at the middle index?

 

No

 

Is the number < (less than) the number at the middle index?

 

Yes

 

So search again on just the left half of the search list:

 

high is changed to mid -1, i.e. 10 - 1 = 9,

low remains unchanged at 10

 

check (low <= high) is now false (we have completed the search with no success)

 

Program output: "Number not found"

 

 

 

 

Step 5

 

Using the pseudocode as a guide, implement a binary search program.

 

Your program should start with a comment block that contains the following information:

 

#  File:       lab9.py

#  Purpose:    Binary search on an ordered list

#  Programmer: [your name]    

#  Partner:    [your partner's name]

#  Course:     CSCI120A

#  Date:       Wednesday 16th March 2005

#  Test data:

 

 

Step 6

 

Test your program by running supplying your own test data. You should test your program with at least 3 sets of test data. Show your test data and results in comments at the top of your program.

 

Step 7

 

At the end of the class, save your program file (lab9.py) and any test text files to your folder on the network in:

 

CSCI120A\Week11\Lab9

 

 

Program points will be based on the following marking scheme:

Marking Scheme: CSCI120A   -   Lab 9  -   Binary Search

Student name(s):

Category

Points

Description

Comments

10

The program is commented appropriately.

Style

20

The source code should use meaningful variable names (identifiers) and be easy to follow.

Output

20

Screen prompts and results should be user-friendly.

Correctness

20

The program should output correct results.

Completeness

20

The program should be complete.

Test

10

Comments in the code explain how the code was tested.