AP CSA 4.14 FRQ Practice: Linear and Binary

Unit 4: Data Collections · Lesson 4.14 · FRQ Practice

Linear and Binary

A free response question in the shape the exam uses: a stated contract, four rubric parts, and no main method handed to you. Worth 4 points.

Back to the Lesson 4.14 pageAll Unit 4 lessons

Why this question is worth four points

Binary search halves the range each pass, and every bug in it is a bound that fails to shrink. This question asks for the number of comparisons alongside the answer, so a search that finds the right element by doing linear work is visibly not a binary search.

What you are given

The driver builds a SORTED int array and passes it to your methods. Write a class named Searcher. Do not write a main method.

The question

  1. (a) public static int linear(int[] data, int target) returns the first index holding target, or -1.
  2. (b) public static int binary(int[] data, int target) returns AN index holding target, or -1. The array is sorted.
  3. (c) public static int binarySteps(int[] data, int target) returns how many times the loop body of your binary search runs.
  4. (d) public static boolean contains(int[] data, int target) returns whether target is present.

What the reader is looking for

  1. Write class Searcher with the four static methods described. No main method.
  2. A binary search keeps a low and a high index and moves one of them PAST the midpoint every pass. Setting low = mid rather than mid + 1 never terminates.
  3. Part (c) counts the passes of the same loop, so it must have the same shape as part (b).

Worked examples

These show what a correct answer prints. There are more cases you cannot see, and they use different values, so an answer built around just these numbers will fail.

Example 1 input
7
1 3 5 7 9 11 13
9
Example 1 output
4
true
3
true
Example 2 input
8
2 4 6 8 10 12 14 16
16
Example 2 output
7
true
4
true

Your answer

Main.java

Input for the Run button

How this is scored: your answer runs against every test case, and the fraction it passes becomes your score out of 4. That is not how a human AP reader marks a rubric, so treat the score as a check on whether your code works, and the rubric above as the thing you are actually practising.


  

  
Stuck?

    
Hint 1
The driver prints whether the binary search FOUND the target rather than which index it landed on, because with repeated values a correct binary search may legitimately return any of them.

    
Hint 2
The step count is what separates a real binary search from a loop wearing its name. On sixteen sorted elements a binary search never needs more than five passes.

    
Hint 3
Move low to mid + 1 and high to mid - 1. Using mid itself leaves the range the same size and the loop never ends.



  
Before you submit

  
4 mistake(s) that lose points on this question
    
Each of these is a real error the grader catches. Check your answer against them before you submit, not instead of trying.

    
    
      
  • the binary search never checks the last remaining element
    • 
      
  • the binary search moves the wrong bound, so it searches the wrong half
    • 
      
  • part (a) returns the last match rather than the first
    • 
      
  • part (d) treats a -1 result as found
    • 
    

  


  
Where to go next

  

    Rework the Lesson 4.14 page
    Try the from-scratch exercise for this lesson
    Try the debugging exercise for this lesson
  


  
  






  

















  
Get in Touch

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







  
Just want free AP CS resources?

  

    Enter your email below and check the subscribe box — no message needed.
    Students get daily practice questions and study tips. Teachers get curriculum resources and teaching strategies.
  







  
  Typically responds within 24 hours






  
✓

  
Message Sent!

  

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







  


  

    
    

    
    

      

        
        
      

      

        
        
      

    


    
    

      

        
        
      

      

        
        
      

    


    
    

      

        
        
      

      

        
        
      

    


    
    

      
🏫 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.
      

    


    
    

      
      
    


    
    

    
    

      
    

  







  

    ✉
    
Email

    
[email protected]

  

  

    📚
    
Courses

    
AP CSA, CSP, & Cybersecurity

  

  

    ⏱
    
Response Time

    
Within 24 hours

  







  Prefer email? Reach me directly at
  [email protected]