December 1999
AP207 : ADVANCED PROGRAMMING TECHNIQUES

QUESTION 5

Total Marks: 15 Marks

• Question 1
• Question 2
• Question 3
• Question 4
• Cover Page

SUGGESTED SOLUTIONS
Solutions and allocated marks are indicated in green.
Return to Question 5

Briefly describe the Binary Search algorithm.

A binary search works by

•Comparing the value in the middle of the list with the key, and sub dividing this search to the lower half if it is greater, or the upper half if it is less,(1 mark)

•Until the element is found, or the list cannot be further sub-divided. (1 mark)

[2]

State the worst case number of comparisons needed to perform a complete Binary Search on a list of size N.

At most,passes will be required.

[1]

Given the sorted list x below, show how the positions of the indicators Left (L ),Right (R )and Middle (M )evolve during a binary search for the number 23.

x =[5 ,12 ,16 ,17 ,23 ,50 ,62 ,100 ]

Each stage should be represented as the following:

•Stage 1:L =5, R =100, M =17 (1 mark)

•Stage 2:L =23, R =100, M =17 (1 mark)

•Stage 3:L =23, R =100, M =50 (1 mark)

•Stage 4:L =23, R =23, M =50 (1 mark)

•Stage 5:L =23, R =23, M =23 (1 mark)

[5]

Write a function BSearch, the signature of which is given below, which takes a sorted list x of type ListType, a integer y specifying the length of the list, and a search term z of type ListElement, which is the type of data held in the list, and searches the list for the search term using the binary search algorithm.The function should return the position of the item in the list if it is present, or -1 otherwise. In your function, you can use the list interface function DataAt, the signature of which is also given below, which will return the value of the data item stored at position y in the list
x.You are not required to implement DataAt .

FUNCTION DataAt(x : ListType, y : INTEGER) : ListElement;

FUNCTION BSearch(x : ListType, y : INTEGER, z : ListElement):
INTEGER;

A sample definition of BSearch follows:

FUNCTION BinarySearch(x : ListType, y : INTEGER, z : ListElement) : INTEGER;
VAR High, Low, Mid : INTEGER;
BEGIN
      High := y;
      Low := 1;
      WHILE (Low <=High) DO
      BEGIN
            Mid := (High +Low) DIV 2;
            IF (Key =DataAt(x, Mid)) THEN
                 BinarySearch:= Mid
            ELSE
                 IF z < DataAt(x, Mid) THEN
                     High:= Mid - 1
                 ELSE
                     Low:= Mid + 1;
      END;
      BinarySearch:= -1;
END;

The following marking scheme should be used:

•Setting High and Low to their respective ends of the list;(1 mark)

•Declaring a loop which is bound by the inequality of High and Low ;(1 mark)

•Setting Mid to the middle value on each iteration;(1 mark)

•Comparing the value at the current Mid of the list using DataAt
(1 mark)

•Returning Mid if it is equal to the search term;(1 mark)

•Reassigning High or Low based on the comparison with the current term;(1 mark)

•Returning -1 if the whole list has been searched without a successful match; (1 mark)

[7]