Small Steps III — Thinking with Programs
Search by Halving
Search by Halving
Explore one topic in small steps. Try the examples one at a time and take a break whenever you need. Choose how many extra exercises you want to try.
Halving the search range
What you will learn
Binary search compares with the middle value and repeatedly halves the possible range. The array must first be sorted from smallest to largest.
Try it
int binary_search(Array<int> numbers, int value)
{
int left = 0;
int right = numbers.length() - 1;
while (left <= right)
{
int middle = (left + right) / 2;
if (numbers[middle] == value)
return middle;
if (value < numbers[middle])
right = middle - 1;
else
left = middle + 1;
}
return -1;
}
void small_main()
{
Array<int> numbers = {1, 3, 5, 7, 9, 11, 13};
print(binary_search(numbers, 11));
}
left and right mark the remaining range's ends. If the target is smaller than the middle value, discard the right half; if larger, discard the left half.
11 is at position 5. Return -1 if not found. Because middle was already checked, exclude it from the next range.
Seeing which values were compared
What you will learn
Printing intermediate values lets you trace how a program finds its answer.
Try it
void small_main()
{
Array<int> numbers = {2, 5, 8, 12, 16, 23, 38, 56};
int value = 23;
int left = 0;
int right = numbers.length() - 1;
int comparisons = 0;
while (left <= right)
{
int middle = (left + right) / 2;
comparisons = comparisons + 1;
print("Checking ", numbers[middle]);
if (numbers[middle] == value)
break;
if (value < numbers[middle])
right = middle - 1;
else
left = middle + 1;
}
print("Comparisons: ", comparisons);
}
The example searches for 23 and prints Checking 12 and Checking 23. There are 2 comparisons.
This example is for observing comparisons. Changing value to an absent value ends the loop when the range becomes empty, but it does not print a separate success message.
Exercise
Write Binary Search to find 23 in the sorted array {4, 8, 15, 16, 23, 42} and print its index.
void small_main()
{
Array<int> numbers = {4, 8, 15, 16, 23, 42};
int value = 23;
int index = -1;
// Binary Search here.
print(index);
}
Hint
Use left, right, and middle, reducing the range by half each time.
show solution
void small_main()
{
Array<int> numbers = {4, 8, 15, 16, 23, 42};
int value = 23;
int index = -1;
int left = 0;
int right = numbers.length() - 1;
while (left <= right)
{
int middle = (left + right) / 2;
if (numbers[middle] == value)
{
index = middle;
break;
}
if (value < numbers[middle])
right = middle - 1;
else
left = middle + 1;
}
print(index);
}
Try More (Optional)
Exercise
Add a counter to Binary Search and print how many comparisons it made to find the value.
void small_main()
{
Array<int> numbers = {1, 3, 5, 7, 9, 11, 13, 15, 17};
int value = 17;
int comparisons = 0;
// Binary Search and count comparisons.
print("Comparisons: ", comparisons);
}
Hint
Increase comparisons by 1 each time the while loop runs.
show solution
void small_main()
{
Array<int> numbers = {1, 3, 5, 7, 9, 11, 13, 15, 17};
int value = 17;
int comparisons = 0;
int left = 0;
int right = numbers.length() - 1;
while (left <= right)
{
int middle = (left + right) / 2;
comparisons = comparisons + 1;
if (numbers[middle] == value)
break;
if (value < numbers[middle])
right = middle - 1;
else
left = middle + 1;
}
print("Comparisons: ", comparisons);
}