AP® Computer Science A glossary
Binary search
Course: AP® Computer Science A Shows up in: Unit 4: Data Collections
A search algorithm for sorted data that checks the middle element and eliminates half of the remaining elements each step.
Appears in the course and exam description (CED): 4.17.B.14.17.B.24.17.B.3
Binary search requires data in sorted order. It compares the target with the middle element, then continues in the only half that can still hold the target, until it finds the value or no elements are left. It can be written iteratively or recursively and is typically more efficient than linear search: about 10 checks for 1,000 elements.
Example
int low = 0;
int high = arr.length - 1;
while (low <= high)
{
int mid = (low + high) / 2;
if (arr[mid] == target)
{
return mid;
}
else if (arr[mid] < target)
{
low = mid + 1;
}
else
{
high = mid - 1;
}
}
return -1;