Searching Algorithms

IB Syllabus: B2.4.2 & B2.4.3: Construct and trace algorithms to implement a linear search and a binary search for data retrieval.

Table of Contents

  1. Key Concepts
  2. Linear Search
    1. How It Works
    2. Java Code (Inline in Main)
    3. Trace: Search for 75
    4. Pseudocode (Method Version)
    5. Linear Search Quick Check
    6. Linear Search Trace Exercise
    7. Linear Search Code Completion
    8. Linear Search Spot the Bug
    9. Linear Search Output Prediction
    10. Linear Search Practice
  3. Binary Search
    1. How It Works
    2. Java Code (Inline in Main)
    3. Trace: Search for 70
    4. Trace: Search for 55 (Not Found)
    5. Pseudocode (Method Version)
    6. Binary Search Quick Check
    7. Binary Search Trace Exercise (Found)
    8. Binary Search Trace Exercise (Not Found)
    9. Binary Search Code Completion
    10. Binary Search Spot the Bug
    11. Binary Search Output Prediction
    12. Binary Search Practice
  4. Linear vs Binary Search
    1. Scaling Example
  5. Combined Exercises
    1. Combined Quick Check
    2. Combined Practice
  6. GitHub Classroom
  7. Connections

Key Concepts

A search algorithm finds whether a target value exists in a collection and, if so, at which position (index). The two fundamental approaches are:

  Linear Search Binary Search
Also called Sequential search Half-interval search
Requirement None, works on any array Array must be sorted
Strategy Check every element one by one Eliminate half the remaining elements each step
Complexity O(n) O(log n)
Algorithm type Brute force / iterative Divide and conquer

Understanding when to use each algorithm matters as much as knowing how they work. Linear search is simpler but slower on large data. Binary search is faster but requires a sorted array, and sorting has its own cost.

Quick String Reminder: The examples on this page search int arrays with ==. When searching String arrays, use .equals() to check for a match. For binary search on Strings, use .compareTo() to decide which half to search: it returns a negative number if the first string comes before the second alphabetically, zero if they are equal, and a positive number if it comes after. For example: "apple".compareTo("banana") returns a negative value because "apple" comes before "banana".

How It Works

A linear (sequential) search examines each item in turn and compares it to the target value. The search starts at the beginning and continues until the item is found or the entire array has been checked.

Index:    0    1    2    3    4    5    6    7
        ┌────┬────┬────┬────┬────┬────┬────┬────┐
  arr:  │  3 │ 15 │  2 │  8 │  7 │  1 │ 14 │ 38 │
        └────┴────┴────┴────┴────┴────┴────┴────┘
          ↓    ↓    ↓    ↓    ↓    ...
        start here → go through each → to the end → stop

Common uses:

  • Searching unsorted collections
  • Reading through text/CSV files line by line
  • Small arrays where simplicity matters more than speed

Java Code (Inline in Main) 

int[] numbers = {10, 1, 32, 41, 16, 60, 75, 82, 90, 11};

int target = 75;
boolean found = false;

for (int i = 0; i < numbers.length && !found; i++) {
    if (numbers[i] == target) {
        found = true;
        System.out.println("Found at index: " + i);
    }
}

if (!found) {
    System.out.println("The number does not exist.");
}

The && !found condition in the loop is important. It provides an early exit so the loop stops as soon as the target is found. Without it, the loop would continue checking every remaining element unnecessarily.

Trace: Search for 75

i numbers[i] == 75? found
0 10 false false
1 1 false false
2 32 false false
3 41 false false
4 16 false false
5 60 false false
6 75 true true → stop

Output: Found at index: 6

Pseudocode (Method Version)

The method version below uses pseudocode. We will implement search algorithms as proper Java methods after covering Methods & Modularisation (B2.3.4).

sequentialSearch(array[], SIZE, VALUE)
    INDEX = 0
    loop while (INDEX < SIZE)
        if (array[INDEX] == VALUE) then
            return INDEX
        end if
        INDEX = INDEX + 1
    end loop
    return -1       // not found

Analysis:

  • If we find the value, we return its index
  • If we reach the end without finding it, we return -1 as an error indicator
  • Best case: O(1), target is the first element
  • Worst case: O(n), target is the last element or not in the array at all
Linear Search Algorithm Explained
Linear Search Algorithm Explained

Linear Search Quick Check

Q1. What is the worst-case time complexity of linear search?

Q2. When is linear search the better choice over binary search?

Q3. What is the best-case time complexity of linear search?

Linear Search Trace Exercise

Trace a linear search for 41 in {10, 1, 32, 41, 16, 60}. Fill in each row as the loop executes.

inumbers[i]== 41?found
0
1
2
3

Found at index:

Linear Search Code Completion

Complete the linear search code that searches for a target value in an array and prints whether it was found and at which index.

This algorithm iterates through an array checking each element against the target. The && !found condition ensures the loop stops early once the target is located.

int[] data = {5, 18, 3, 27, 11, 42, 9};
int target = 27;
boolean found = ;

for (int i = 0; i <  && !found; i++) {
    if () {
        found = true;
        System.out.println("Found at index: " + );
    }
}

Linear Search Spot the Bug

This linear search finds the target but continues looping unnecessarily after finding it. Click the buggy line, then pick the fix.

1int[] numbers = {34, 67, 12, 67, 45}; 2int target = 67; 3boolean found = false; 4for (int i = 0; i < numbers.length; i++) { 5 if (numbers[i] == target) { 6 found = true; 7 System.out.println("Found at index: " + i); 8 } 9}

Pick the correct fix for line 4:

Linear Search Output Prediction

This code performs a linear search for the value 20 in a small array. The loop stops early when the target is found. What is the exact output?

int[] arr = {5, 8, 20, 14, 3};
boolean found = false;
for (int i = 0; i < arr.length && !found; i++) {
    if (arr[i] == 20) {
        found = true;
        System.out.println("Index: " + i);
    }
}
if (!found) {
    System.out.println("Not found");
}

Type your answer:

Linear Search Practice

  1. Find a Name. Given String[] names = {"Alice", "Bob", "Charlie", "Diana", "Eve"}, write code in main that searches for "Charlie" and prints the index where it is found, or "Not found" if absent. Remember to use .equals() for String comparison.

  2. Count Comparisons. Modify the linear search code to count and print the total number of comparisons made before finding (or not finding) the target.

  3. Search for the Last Occurrence. Given int[] data = {5, 12, 8, 12, 3, 12, 7}, write a linear search that finds and prints the last index where 12 appears. (Hint: do not use !found as the exit condition.)

  4. Not Found Case. Trace a linear search for 99 in {15, 33, 8, 72, 50} on paper. Complete the table for all 5 iterations and confirm the output is “not found”.

How It Works

Binary search looks for an item in an already sorted array by eliminating large portions of the data on each comparison. It works by comparing the target value to the middle element of the array:

  • If they are equal → found!
  • If target is smaller than middle → search the left half
  • If target is larger than middle → search the right half
                         mid
                    (first + last) / 2
  first                                    last
    ↓                    ↓                    ↓
┌────┬────┬────┬────┬────┬────┬────┐
│  0 │ 10 │ 30 │ 40 │ 50 │ 60 │ 70 │
└────┴────┴────┴────┴────┴────┴────┘
  0    1    2    3    4    5    6

  target > arr[mid]  →  search right half (first = mid + 1)
  target < arr[mid]  →  search left half  (last = mid - 1)

Binary search only works on sorted arrays. On an unsorted array, it may eliminate the wrong half and miss the target entirely, without any error message. Always confirm the array is sorted first.

Java Code (Inline in Main) 

int[] numbers = {0, 10, 30, 40, 50, 60, 70, 80, 90, 100};

int target = 70;
int first = 0;
int last = numbers.length - 1;
boolean found = false;
int middle;

while (first <= last && !found) {
    middle = (first + last) / 2;

    if (target == numbers[middle]) {
        found = true;
        System.out.println("Found at index: " + middle);
    } else if (target < numbers[middle]) {
        last = middle - 1;
    } else {
        first = middle + 1;
    }
}

if (!found) {
    System.out.println("The number does not exist.");
}

Trace: Search for 70

Array: {0, 10, 30, 40, 50, 60, 70, 80, 90, 100}

Step first last middle numbers[middle] Decision
1 0 9 4 50 70 > 50 → first = 5
2 5 9 7 80 70 < 80 → last = 6
3 5 6 5 60 70 > 60 → first = 6
4 6 6 6 70 Found!

Output: Found at index: 6

Only 4 comparisons to find the target in a 10-element array. Linear search would have needed 7.

Trace: Search for 55 (Not Found)

Step first last middle numbers[middle] Decision
1 0 9 4 50 55 > 50 → first = 5
2 5 9 7 80 55 < 80 → last = 6
3 5 6 5 60 55 < 60 → last = 4
4 first (5) > last (4) - - - Loop ends, not found

Pseudocode (Method Version)

As with linear search, the method version will be implemented in Java after covering Methods (B2.3.4).

binarySearch(array[], SIZE, VALUE)
    LOW = 0
    HIGH = SIZE - 1
    loop while (LOW <= HIGH)
        MID = (LOW + HIGH) / 2
        if (array[MID] == VALUE) then
            return MID
        else if (array[MID] < VALUE) then
            LOW = MID + 1
        else
            HIGH = MID - 1
        end if
    end loop
    return -1       // not found

Analysis:

  • At each step, the search space is reduced by half
  • If the middle value equals the target, return the middle index
  • If the target is smaller, search the left half (HIGH = MID - 1)
  • If the target is larger, search the right half (LOW = MID + 1)
  • Return -1 if the loop ends without finding the target
  • Best case: O(1), target is exactly in the middle
  • Average/Worst case: O(log n), halving each time
Binary Search Algorithm Explained
Binary Search Algorithm Explained

Binary Search Quick Check

Q1. What is the worst-case time complexity of binary search?

Q2. What happens if you run binary search on the unsorted array {50, 12, 34, 7, 90} searching for 7?

Q3. In binary search, what does the condition first <= last check?

Q4. A sorted array has 128 elements. What is the maximum number of comparisons binary search needs?

Binary Search Trace Exercise (Found)

Search for 30 in {10, 20, 30, 40, 50, 60, 70}. Indices: 0=10, 1=20, 2=30, 3=40, 4=50, 5=60, 6=70.

Stepfirstlastmiddlenumbers[middle]Decision
1
2
3

Found at index:

Binary Search Trace Exercise (Not Found)

Search for 45 in {10, 20, 30, 40, 50, 60, 70}. Fill in each step until the loop ends.

Indices: 0=10, 1=20, 2=30, 3=40, 4=50, 5=60, 6=70

Stepfirstlastmiddlenumbers[middle]Decision
1
2
3

After step 3, last becomes which is less than first (), so the loop ends.

Was 45 found?

Binary Search Code Completion

Complete the binary search code that searches a sorted array for a target value.

This algorithm repeatedly halves the search space by comparing the target to the middle element. It adjusts the first and last boundaries to narrow in on the target.

int[] sorted = {5, 12, 18, 27, 33, 42, 56};
int target = 33;
int first = 0;
int last = sorted.length - 1;
boolean found = false;

while ( && !found) {
    int middle = ;

    if (target == sorted[middle]) {
        found = true;
        System.out.println("Found at index: " + middle);
    } else if (target < sorted[middle]) {
        ;
    } else {
        ;
    }
}

Binary Search Spot the Bug

This binary search has a boundary update error that causes it to search the wrong half of the array. Click the buggy line, then pick the fix.

1int[] sorted = {10, 20, 30, 40, 50, 60, 70}; 2int target = 20; 3int first = 0; 4int last = sorted.length - 1; 5boolean found = false; 6while (first <= last && !found) { 7 int middle = (first + last) / 2; 8 if (target < sorted[middle]) { first = middle - 1; } 9 else if (target > sorted[middle]) { first = middle + 1; } 10 else { found = true; System.out.println("Found at: " + middle); } 11}

Pick the correct fix for line 8:

Binary Search Output Prediction

This code performs a binary search for 25 in a sorted array. Trace through the loop iterations carefully. What is the exact output?

int[] sorted = {10, 20, 30, 40, 50, 60, 70};
int target = 25;
int first = 0;
int last = sorted.length - 1;
boolean found = false;
while (first <= last && !found) {
    int middle = (first + last) / 2;
    if (target == sorted[middle]) {
        found = true;
    } else if (target < sorted[middle]) {
        last = middle - 1;
    } else {
        first = middle + 1;
    }
}
System.out.println(found);

Type your answer:

Binary Search Practice

  1. Trace on Paper. Given the sorted array {5, 12, 18, 24, 33, 42, 56, 71}, trace a binary search for 42. Write out each step showing first, last, middle, and the decision made.

  2. Trace Not Found. Using the same sorted array {5, 12, 18, 24, 33, 42, 56, 71}, trace a binary search for 25 (not in the array). Show all steps until the loop terminates.

  3. Parallel Arrays. Two arrays store student IDs and names: 
    int[] id = {1001, 1002, 1050, 1100, 1120, 1180, 1200, 1400};
String[] name = {"Apple", "Cherry", "Peach", "Banana", "Fig", "Grape", "Olive", "Mango"};

    Write a binary search that takes a target ID and prints the corresponding name. If the ID is not found, print a “not found” message.

  4. Search and Report. Given a sorted array {3, 8, 15, 22, 29, 36, 43, 50}, write code that uses binary search to find a user-entered target, prints how many comparisons were made, and prints whether the value was found and at which index.

  5. Why does binary search fail on unsorted data? Give a concrete example with 5 elements where binary search produces a wrong result, and explain which half gets incorrectly eliminated.
Feature Linear (Sequential) Binary
Speed on large data Much slower, checks every element Much faster, halves each step
Time complexity O(n) O(log n)
Comparisons needed Up to n Up to log&sub2;(n)
Requires sorted data? No, works on any array Yes, must be sorted first
Sorting cost None Sorting adds computational cost
Simplicity Simpler to construct More complex logic
Algorithm strategy Iterative / brute force Divide and conquer

Scaling Example

Array size (n) Linear (worst case) Binary (worst case)
10 10 comparisons 4 comparisons
100 100 comparisons 7 comparisons
1,000 1,000 comparisons 10 comparisons
1,000,000 1,000,000 comparisons 20 comparisons

Binary search on 1 million elements needs at most 20 comparisons. That is the power of O(log n): the work barely increases as the data grows.

Combined Exercises

These exercises require you to use both search algorithms or compare them directly.

Combined Quick Check

Q1. A student says “binary search is always better than linear search.” What is the flaw in this statement?

Q2. When does the cost of sorting before binary search become worthwhile?

Q3. A sorted array has 1024 elements. How many comparisons does binary search need at most?

Combined Practice

  1. Compare Both Searches. Write a program that creates a sorted array of 20 elements (values 5, 10, 15, …, 100). Search for a user-entered value using both linear search and binary search. For each, count the number of comparisons made and print a comparison of efficiency.

  2. Choose the Right Algorithm. For each scenario, state whether you would use linear search or binary search and explain why:
    • (a) Searching a phone book for a name
    • (b) Finding a specific card in a shuffled deck
    • (c) Looking up a word in a dictionary
    • (d) Checking if a student ID exists in an unsorted attendance list

  3. Game Inventory Search. Create an array of 8 game item names (sorted alphabetically). Write code that lets the user type an item name and uses binary search to check if it exists. If found, print “Item found in inventory!”. If not, print “Item not in inventory.” Remember to use .equals() for String comparison and .compareTo() for determining which half to search.

  4. Efficiency Analysis. An online store has a database of 1,000,000 product IDs (sorted). A customer searches for a product. (a) How many comparisons would linear search need in the worst case? (b) How many would binary search need? (c) If each comparison takes 1 microsecond, how long does each algorithm take in the worst case?

GitHub Classroom

Searching Algorithms
Practice implementing linear search and binary search on arrays of integers and strings.
Core Open in GitHub

Connections

  • Prerequisites: 1D Arrays (arrays are the structure being searched), Iteration (loops drive both algorithms), Selection (if/else for comparisons)
  • Related: Sorting Algorithms (sorting is required before binary search can be used)
  • Forward: After covering Methods (B2.3.4), both search algorithms will be refactored into reusable methods
  • Big O Notation will be covered in detail after sorting algorithms. For now, know that linear search is O(n) and binary search is O(log n)

Back to top

© EduCS.me — A resource hub for IB Computer Science

This site uses Just the Docs, a documentation theme for Jekyll.