AP CSA 4.14 Exercise 1: Scan It, Then Halve It

AP CSA Hub Unit 4 4.1 â–¼ Lesson Ex 1 Ex 2 Quiz 4.2 â–¼ Lesson Ex 1 Ex 2 Quiz 4.3 â–¼ Lesson Ex 1 Ex 2 Quiz 4.4 â–¼ Lesson Ex 1 Ex 2 Quiz 4.5 â–¼ Lesson Ex 1 Ex 2 Quiz 4.6 â–¼ Lesson Ex 1 Ex 2 Quiz 4.7 â–¼ Lesson Ex 1 Ex 2 Quiz 4.8 â–¼ Lesson Ex 1 Ex 2 Quiz 4.9 â–¼ Lesson Ex 1 Ex 2 Quiz 4.10 â–¼ Lesson Ex 1 Ex 2 Quiz 4.11 â–¼ Lesson Ex 1 Ex 2 Quiz 4.12 â–¼ Lesson Ex 1 Ex 2 Quiz 4.13 â–¼ Lesson Ex 1 Ex 2 Quiz 4.14 â–¼ Lesson Ex 1 Ex 2 Quiz 4.15 â–¼ Lesson Ex 1 Ex 2 Quiz 4.16 â–¼ Lesson Ex 1 Ex 2 Quiz 4.17 â–¼ Lesson Ex 1 Ex 2 Quiz

Unit 4: Data Collections · Lesson 4.14 · Exercise 1

Scan It, Then Halve It

Searching Algorithms. Write real Java, run it, and submit it to be graded against hidden test cases.

Back to the Lesson 4.14 pageAll Unit 4 lessons

Why this one is worth doing

Linear search costs nothing to set up and can cost the whole array. Binary search costs a sorted array up front and pays it back in comparisons. This exercise hands you data that is already sorted, on purpose, so the only variable left is which search you run and how many comparisons it takes.

What to write

  1. Read a count, then that many integers, ALREADY in sorted increasing order, then a target value.
  2. Print the index found by a LINEAR search that scans from the front and stops at the first match, or -1 when the target is not present.
  3. Print how many comparisons the linear search made, counting one per element it looked at, including the one that matched.
  4. Print the index found by a BINARY search of the same sorted array, or -1 when the target is not present.
  5. Print how many comparisons the binary search made.

Your program reads

An integer count of at least 1, then that many integers already in sorted increasing order, then a target value.

Your program prints

The linear index, the linear comparison count, the binary index and the binary comparison count.

Worked examples

These are the cases you can see. There are more you cannot, and they use different values, so an answer that prints these numbers as constants will fail.

Example 1 input
7
1 2 3 5 7 8 9
7
Example 1 output
4
5
4
3
Example 2 input
5
1 2 3 4 5
1
Example 2 output
0
1
0
2

Your answer

Main.java

Input for the Run button

Run sends whatever is in the input box below. Submitting runs your program against every test case, including hidden ones with different input.


  

  
Stuck?

    
Hint 1
The array is already sorted for you, on purpose: binary search only works on sorted data, and Sorting Algorithms is its own lesson right after this one.

    
Hint 2
Linear search counts one comparison per element it actually looks at. A target at index 0 costs one comparison; a target that is not there costs the whole length.

    
Hint 3
Binary search throws away half the remaining range on every comparison, which is why it needs so few even on a long array.


  
Where to go next

  

    Rework the Lesson 4.14 page
    Pick another Unit 4 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]