Binary Search in AP CSA: Trace It Step by Step

Binary search is one of the most-tested algorithms on the AP CSA exam. On the 2026 exam, you will trace recursive binary search calls — not write the algorithm. This page teaches you exactly how to trace it, step by step, with the same patterns College Board uses.

🔍 How Binary Search Works

Binary search works by repeatedly dividing the search space in half. It requires a sorted array or ArrayList as a precondition. Here is the core logic:

1. Calculate mid = (left + right) / 2
2. If the target equals the element at mid, return mid
3. If the target is less than the element at mid, search the left half
4. If the target is greater, search the right half
5. If left > right, the target is not found — return -1

📋 Tracing Recursive Calls

The AP exam gives you a recursive implementation like this:

public static int bSearch(int[] arr, int left, int right, int x)
{
    if (right >= left)
    {
        int mid = (left + right) / 2;
        if (arr[mid] == x)
        {
            return mid;
        }
        else if (arr[mid] > x)
        {
            return bSearch(arr, left, mid - 1, x);
        }
        else
        {
            return bSearch(arr, mid + 1, right, x);
        }
    }
    return -1;
}

Trace this with arr = {10, 20, 30, 40, 50} and x = 40:

Answer: 2 total calls, returns 3.

💻 Code Examples — Predict First

Before running each example, write down what you think the output will be. This is the single most effective exam study technique.

Example 1: Target Found Early

int[] vals = {0, 4, 4, 5, 6, 7};
int result = bSearch(vals, 0, vals.length - 1, 4);
System.out.println(result);

Answer: First call: left=0, right=5, mid=2. vals[2] is 4, which equals the target. Returns 2 on the first call. Note: there are two 4s in the array. Binary search found the one at index 2, but it could have found either — it does not guarantee finding the first occurrence.

Example 2: Target Not Found

int[] nums = {10, 20, 30, 40, 50};
int result = bSearch(nums, 0, nums.length - 1, 25);
System.out.println(result);

Trace:

Answer: Returns -1. The method is called 4 times total.

Example 3: ArrayList Version

ArrayList data = new ArrayList<>();
// data contains: [0, 10, 30, 40, 50, 70, 70, 70, 70]
int result = binarySearch(data, 0, 8, 70);

Trace: Call 1: low=0, high=8, mid=4. data.get(4) is 50, which is less than 70. Call 2: low=5, high=8, mid=6. data.get(6) is 70. Returns 6. Note it found one of the 70s — not necessarily the first one.

❌ Common Pitfalls

✏ Practice Questions

Select the best answer for each. Answers appear after you choose.

❓ Frequently Asked Questions