December 1999
AP207 : ADVANCED PROGRAMMING TECHNIQUES

QUESTION 5

Total Marks: 15 Marks

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

Click to access
SUGGESTED SOLUTIONS
for Question 5

Briefly describe the Binary Search algorithm.

[2]

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

[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 ]

[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;

[7]