AP CSA 4.14 Debugging: The Half That Never Gets Searched

Unit 4: Data Collections · Lesson 4.14 · Debugging

The Half That Never Gets Searched

Searching Algorithms. This is not a blank editor: it is someone else's attempt. Find what is wrong, fix it, and submit to be graded against hidden test cases.

Back to the Lesson 4.14 page All Unit 4 lessons

Why debugging is its own skill

Binary search is three lines of logic and two of them are easy to get subtly wrong. This version stops before it has examined the final candidate, and it moves its boundaries the wrong way, so it discards the half that contains the answer.

What is wrong with it

The loop condition is low < high, which exits while one candidate is still unexamined, so a target sitting at the final position is reported as missing. Fix the condition.
The two boundary updates are backwards: when the middle value is too small the search should move UP, and it currently moves down. Swap them.
The linear search below is correct and its result is printed so you can compare the two answers.

The program reads

A count, then that many integers already in increasing order, then a target.

The program should print

Two lines: the index found by binary search, then the index found by linear search. They must agree, and both are -1 when the target is absent.

Worked examples

These show what the FIXED program should print. There are more cases you cannot see, and they use different values, so patching around just these numbers will fail.

Example 1 input

5
1 3 5 7 9
9

Example 1 output

4
4

Example 2 input

5
1 3 5 7 9
1

Example 2 output

0
0

Your answer

Main.java

import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner input = new Scanner(System.in);
    int n = input.nextInt();
    int[] data = new int[n];
    for (int i = 0; i < n; i++) {
      data[i] = input.nextInt();
    }
    int target = input.nextInt();

    int low = 0;
    int high = data.length - 1;
    int found = -1;
    while (low < high) {
      int mid = (low + high) / 2;
      if (data[mid] == target) {
        found = mid;
        break;
      } else if (data[mid] < target) {
        high = mid - 1;
      } else {
        low = mid + 1;
      }
    }
    System.out.println(found);

    int linear = -1;
    for (int i = 0; i < data.length; i++) {
      if (data[i] == target) {
        linear = i;
        break;
      }
    }
    System.out.println(linear);
  }
}

Input for the Run button

Run sends whatever is in the code box below, bugs and all, so you can see the crash or the wrong answer for yourself before you fix anything.

Stuck?

Hint 1

When low equals high there is still exactly one element left to check, at that position. low < high quits without looking at it, so any target that ends up alone in the final window is missed.

Hint 2

Say the boundary update out loud: the middle is too SMALL, so everything from the middle down is too small, so the answer must be HIGHER. That means low moves up to mid + 1. The starter does the opposite.

Hint 3

The linear search is there as an oracle. Any input where the two printed numbers disagree is an input that exposes the bug, so use it to check your fix.

Where to go next

Rework the Lesson 4.14 page Try the from-scratch version of this lesson

Get in Touch

Whether you're a student, parent, or teacher — I'd love to hear from you.

Typically responds within 24 hours

✓

Message Sent!

Thanks for reaching out. I'll get back to you within 24 hours.

Name *

Email *

I am a... (optional)

Which course? (optional)

Phone (optional)

How did you find us? (optional)

🏫 Welcome, fellow educator!

I offer curriculum resources, practice materials, and study guides designed for AP CS teachers. Let me know what you're looking for — whether it's classroom materials, a guest speaker, or Teachers Pay Teachers resources.

Message (optional — leave blank if just subscribing)

✉

[email protected]

📚

Courses

AP CSA, CSP, & Cybersecurity

⏱

Response Time

Within 24 hours

Prefer email? Reach me directly at [email protected]