CS 201  Binary Seach  Exercises  Name: _________________________________

Using the following algothim and the array given, perform the following binary searches. YOU MUST SHOW ALL VALUES OF HIGH, LOW, and MID.

     int list[11];
     int value, low, high, mid,
         

0 07
1 13
2 25
3 37
4 42
5 55
6 67
7 76
8 86
9 92
10 98
N=11; 
BinarySearch(A[0..N-1], value) {
low = 0
high = N - 1
while (low <= high) {
mid = (low + high) / 2
if (A[mid] > value)
high = mid - 1
else if (A[mid] < value)
low = mid + 1
else
return mid // found
}
return -1 // not found
}
Example:
Value= 67
Low=
High=
Mid =
Value Returned =

Answer
Value= 67
Low=  0  6
High= 10   7
Mid =  5   8    6
Value Returned =   6

Value= 86
Low=
High=
Mid =
Value Returned =
Value= 25
Low=
High=
Mid =
Value Returned =
Value= 92
Low=
High=
Mid =
Value Returned =
Value= 42
Low=
High=
Mid =
Value Returned =
Value= 20
Low=
High=
Mid =
Value Returned =
Value= 80
Low=
High=
Mid =
Value Returned =
Value= 60
Low=
High=
Mid =
Value Returned =
Value= 37
Low=
High=
Mid =
Value Returned =