A structured lesson workspace with readable content, hands-on examples, and a clean path to completion.
The classic binary search midpoint calculation is mid = (low + high) / 2. It looks correct. It is wrong. If low and high are both large positive integers, their sum can overflow a signed int. The result wraps to a negative number. Dividing a negative number by 2 gives a negative midpoint. The array access arr[mid] reads before the start of the buffer. This bug existed in the Java standard library for nine years before it was discovered in 2006. It exists in C codebases to this day.
#include <stdio.h>#include <limits.h>int main(void) {int low = 1500000000;int high = 2000000000;int bad_mid = (low + high) / 2;printf("Unsafe: (%d + %d) / 2 = %d\n", low, high, bad_mid);int good_mid = low + (high - low) / 2;printf("Safe: %d + (%d - %d) / 2 = %d\n", low, high, low, good_mid);int unsigned_mid = (int)(((unsigned int)low + (unsigned int)high) / 2);printf("Unsigned cast: %d\n", unsigned_mid);return 0;}
The unsafe version overflowed and produced a negative midpoint. The safe version computes the difference first, which cannot overflow because high >= low in a valid binary search. The unsigned cast version works because unsigned overflow is well-defined (it wraps), and the sum of two values that fit in int will fit in unsigned int. Both safe versions produce the correct midpoint: 1750000000.
#include <stdio.h>int binary_search(const int *arr, int n, int target) {int low = 0;int high = n - 1;while (low <= high) {int mid = low + (high - low) / 2;if (arr[mid] == target) return mid;if (arr[mid] < target) low = mid + 1;else high = mid - 1;}return -1;}int main(void) {int arr[] = {2, 5, 8, 12, 16, 23, 38, 45, 56, 72, 91};int n = 11;printf("Search 23: index %d\n", binary_search(arr, n, 23));printf("Search 99: index %d\n", binary_search(arr, n, 99));return 0;}
This is a one-line fix for a bug that hid in production code for decades. The lesson is not just about binary search. It is about questioning every arithmetic expression that adds two values of the same sign. The overflow is silent. The consequence is an out-of-bounds access. The fix is a different way of computing the same value. Next: converting a for loop to a while loop, and when each is appropriate.
Finish the lesson once you have worked through the material. This awards ★ 30 XP.