Linear and Binary Search

All 15 linear and binary search questions

Work through the interactive quiz above first. This is the full linear and binary search question set with worked solutions, so students can review any question after attempting it.

1. 1.Code Tracing 01 - Linear and Binary Search: track the final printed value.

   int[] data = {4, 9, 2, 7, 5, 1};
   int target = 7;
   int index = -1;
   for (int i = 0; i < data.length; i++) {
     if (data[i] == target && index == -1) index = i;
   }
   System.out.print(index);

   • -1
   • 4
   • The code does not compile.
   • 3
   Show worked solution

   Correct answer: 3

   The linear search records only the first matching index because of the index == -1 guard.

2. 2.Code Tracing 12 - Linear and Binary Search: follow the variable updates.

   int[] data = {4, 5, 6, 8, 8, 10};
   int target = 8;
   int low = 0, high = data.length - 1, checks = 0;
   while (low <= high) {
     checks++;
     int mid = (low + high) / 2;
     if (data[mid] == target) break;
     else if (data[mid] < target) low = mid + 1;
     else high = mid - 1;
   }
   System.out.print(checks);

   • 2
   • 4
   • 3
   • The code does not compile.
   Show worked solution

   Correct answer: 2

   Binary search repeatedly halves the search range; checks counts how many midpoints are examined.

3. 3.Code Tracing 28 - Linear and Binary Search: trace the branch and loop path.

   import java.util.Arrays;
   public class Main {
     public static void main(String[] args) {
       int[] data = {13, 4, 8, 7, 6};
       int minIndex = 0;
       for (int j = 1; j < data.length; j++) {
         if (data[j] < data[minIndex]) minIndex = j;
       }
       int temp = data[0]; data[0] = data[minIndex]; data[minIndex] = temp;
       System.out.print(Arrays.toString(data));
     }
   }

   • [4, 13, 8, 7, 6]
   • [13, 4, 8, 7, 6]
   • [4, 6, 7, 8, 13]
   • [6, 7, 8, 13, 4]
   Show worked solution

   Correct answer: [4, 13, 8, 7, 6]

   This performs only the first selection-sort pass, moving the smallest value into index 0.

4. 4.Code Tracing 39 - Linear and Binary Search: watch the index changes.

   import java.util.Arrays;
   public class Main {
     public static void main(String[] args) {
       int[] data = {15, 6, 9, 9, 8};
       int key = data[1];
       int j = 0;
       while (j >= 0 && data[j] > key) {
         data[j + 1] = data[j];
         j--;
       }
       data[j + 1] = key;
       System.out.print(Arrays.toString(data));
     }
   }

   • [8, 9, 9, 15, 6]
   • [6, 15, 9, 9, 8]
   • [15, 6, 9, 9, 8]
   • [6, 8, 9, 9, 15]
   Show worked solution

   Correct answer: [6, 15, 9, 9, 8]

   This traces the insertion of the element at index 1 into the sorted prefix before it.

5. 5.Code Tracing 50 - Linear and Binary Search: evaluate the state change step by step.

   int[] data = {13, 9, 6, 8, 8, 10};
   boolean duplicate = false;
   for (int i = 0; i < data.length - 1; i++) {
     for (int j = i + 1; j < data.length; j++) {
       if (data[i] == data[j]) duplicate = true;
     }
   }
   System.out.print(duplicate);

   • 6
   • 0
   • true
   • false
   Show worked solution

   Correct answer: true

   The nested loops compare every pair of different indexes exactly once.

6. 6.What is printed by the following code segment?

   int[] a = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
   int lo = 0;
   int hi = a.length - 1;
   int c = 0;
   while (lo <= hi)
   {
       int mid = (lo + hi) / 2;
       c++;
       if (a[mid] == 91) { lo = hi + 1; }
       else if (a[mid] < 91) { lo = mid + 1; }
       else { hi = mid - 1; }
   }
   System.out.print(c);

   • 4
   • 3
   • 10
   • 5
   Show worked solution

   Correct answer: 4

   The midpoints examined are 16, 38, 72, then 91, so four comparisons are needed.

7. 7.What is printed by the following code segment?

   int[] a = {1, 3, 5, 7, 9, 11};
   int c = 0;
   for (int i = 0; i < a.length; i++)
   {
       c++;
       if (a[i] == 9) { i = a.length; }
   }
   System.out.print(c);

   • 6
   • 5
   • 4
   • 9
   Show worked solution

   Correct answer: 5

   Linear search examines five elements before finding the target at index 4.

8. 8.Roughly how many comparisons does binary search need in the worst case on 1,000,000 sorted values?

   • About 1000
   • About 500,000
   • About 20
   • About 1,000,000
   Show worked solution

   Correct answer: About 20

   Each comparison halves the range, and about twenty halvings reduce a million to one.

9. 9.What is printed by the following code segment?

   int[] a = {1, 2, 3, 4, 5};
   int lo = 0;
   int hi = a.length - 1;
   int mid = -1;
   while (lo <= hi)
   {
       mid = (lo + hi) / 2;
       if (a[mid] == 6) { lo = hi + 1; }
       else if (a[mid] < 6) { lo = mid + 1; }
       else { hi = mid - 1; }
   }
   System.out.print(lo + " " + mid);

   • 4 4
   • 5 5
   • -1 4
   • 5 4
   Show worked solution

   Correct answer: 5 4

   The target is larger than every element, so the low bound runs past the end and the last midpoint examined is the final index.

10. 10.What is printed by the following code segment?

    int[] a = {4, 4, 4, 4};
    int lo = 0;
    int hi = a.length - 1;
    int mid = 0;
    while (lo <= hi)
    {
        mid = (lo + hi) / 2;
        if (a[mid] == 4) { lo = hi + 1; }
        else { hi = mid - 1; }
    }
    System.out.print(mid);

    • 1
    • 0
    • 3
    • 2
    Show worked solution

    Correct answer: 1

    With duplicates the search stops at the first midpoint it examines, which is index 1.

11. 11.Which statement about the code below is true?

    int[] a = {5, 2, 9};
    // binary search for 2 is performed on a

    • It always finds 2 because the array is short.
    • It may report that 2 is absent, because the array is not sorted.
    • It throws an exception because the array is unsorted.
    • It sorts the array first.
    Show worked solution

    Correct answer: It may report that 2 is absent, because the array is not sorted.

    Unsorted input produces a wrong answer rather than an error, which is what makes the mistake hard to detect.

12. 12.What is printed by the following code segment?

    int[] a = {3, 6, 9, 12};
    int t = 9;
    int pos = -1;
    for (int i = a.length - 1; i >= 0; i--)
    {
        if (a[i] == t) { pos = i; }
    }
    System.out.print(pos);

    • -1
    • 3
    • 2
    • 1
    Show worked solution

    Correct answer: 2

    The backward loop still finds the single match, which sits at index 2.

13. 13.What is printed by the following code segment?

    int[] a = {1, 4, 9, 16, 25};
    int c = 0;
    int lo = 0;
    int hi = a.length - 1;
    while (lo < hi)
    {
        int mid = (lo + hi) / 2;
        c++;
        if (a[mid] < 16) { lo = mid + 1; }
        else { hi = mid; }
    }
    System.out.print(lo + " " + c);

    • 3 3
    • 2 2
    • 4 3
    • 3 2
    Show worked solution

    Correct answer: 3 2

    This variant narrows to the first element at least 16 rather than stopping on an exact match.

14. 14.What is printed by the following code segment?

    int[] a = {10, 20, 30};
    int c = 0;
    for (int v : a)
    {
        c++;
        if (v > 15) { break; }
    }
    System.out.print(c);

    • 2
    • 1
    • 3
    • 0
    Show worked solution

    Correct answer: 2

    The search stops at the first element above the threshold, having examined two.

15. 15.Which precondition must hold for binary search to be correct?

    • The elements must be distinct.
    • The elements must be in sorted order.
    • The number of elements must be even.
    • The elements must be positive.
    Show worked solution

    Correct answer: The elements must be in sorted order.

    Ordering is what makes discarding half the range safe. Duplicates, count, and sign are all irrelevant.