Searching Algorithms - AP Computer Science A Study Guide

Getting Started

When working with collections of data, such as arrays, a fundamental task is to determine if a specific value is present. Imagine searching for a contact in your phone or a book in a library; the strategy you use matters. In Java, we use searching algorithms to perform this task efficiently, and the choice of algorithm can have a significant impact on a program's performance, especially when dealing with large datasets.

What You Should Be Able to Do

• Implement a sequential (linear) search to find an element in an array.

• Implement a binary search to find an element in a sorted array.

• Explain why a binary search requires the data to be sorted beforehand.

• Compare the performance characteristics of sequential and binary search.

• Trace the key variables and comparisons made during a sequential or binary search.

Key Concepts & Java Implementation

The Core Idea: Two Strategies for Finding Data

An algorithm is a step-by-step set of instructions for solving a problem. When the problem is "find an item in a list," we have two primary algorithms to consider: sequential search and binary search. They differ greatly in their approach and efficiency.

Sequential (Linear) Search

The sequential search is the most straightforward approach. It begins at the first element of an array and checks each element, one after another, in sequence, until it either finds the target value or reaches the end of the array. This is like looking for a specific page in a book by flipping through every single page from the beginning.

This algorithm has the advantage of simplicity and works on any array, regardless of whether the data is sorted or not.

Syntax & Implementation

A sequential search is typically implemented with a for loop that iterates from the first index (0) to the last (array.length - 1). The method should return the index of the element if found, and a conventional value like -1 if the element is not present in the array.

/**

 * Searches for a target value in an integer array using a sequential search.

 * @param arr The array to search through.

 * @param target The value to find.

 * @return The index of the first occurrence of the target, or -1 if not found.

 */

public static int sequentialSearch(int[] arr, int target) {

    // Iterate through each element of the array from the beginning.

    for (int i = 0; i < arr.length; i++) {

        // Check if the current element matches the target.

        if (arr[i] == target) {

            return i; // Target found, return its index immediately.

        }

    }

    // If the loop finishes, the target was not in the array.

    return -1;

}

Tracing & Analysis

Let's trace a search for the number 11 in the array [2, 8, 1, 11, 5].

Analysis: In the worst-case scenario (the target is the last element or not in the array), a sequential search must examine every single element. Therefore, the number of comparisons is directly proportional to the size of the array, n.

Binary Search

The binary search is a much more efficient "divide and conquer" algorithm, but it comes with a critical requirement: the array must be sorted.

It works by repeatedly dividing the search interval in half. It first compares the target value to the middle element of the array.

• If they match, the search is over.

• If the target is less than the middle element, it narrows the search to the lower (left) half of the array.

• If the target is greater than the middle element, it narrows the search to the upper (right) half.

This process repeats until the value is found or the interval is empty. This is like looking up a word in a dictionary: you open to the middle, see if your word is on that page, and then decide whether to search the first half or the second half of the book.

Syntax & Implementation

A binary search is implemented with a while loop and three integer variables to keep track of the search interval: low, high, and mid.

/**

 * Searches for a target value in a SORTED integer array using a binary search.

 * @param arr The sorted array to search through.

 * @param target The value to find.

 * @return The index of the target, or -1 if not found.

 */

public static int binarySearch(int[] arr, int target) {

    int low = 0;                  // The starting index of the search interval.

    int high = arr.length - 1;    // The ending index of the search interval.


    // Continue as long as the search interval is valid.

    while (low <= high) {

        // Calculate the middle index.

        int mid = low + (high - low) / 2;


        // Case 1: The middle element is our target.

        if (arr[mid] == target) {

            return mid; // Target found!

        }

        // Case 2: The target is smaller, so it must be in the left half.

        else if (target < arr[mid]) {

            high = mid - 1; // Adjust the 'high' boundary.

        }

        // Case 3: The target is larger, so it must be in the right half.

        else {

            low = mid + 1;  // Adjust the 'low' boundary.

        }

    }

    // If the loop finishes, the target was not in the array.

    return -1;

}

Tracing & Analysis

Let's trace a search for the number 25 in the sorted array [4, 8, 12, 16, 23, 25, 31, 42].

Analysis: With each comparison, binary search eliminates half of the remaining elements. This makes it extremely fast for large arrays. For an array with a million sorted items, binary search will take at most 20 comparisons, whereas a sequential search could take up to a million.

Java Syntax Quick-Reference

• array.length: A property that holds the total number of elements in an array.

• array[index]: The square bracket operator used to access the element at a specific index.

• while (condition): A loop that continues to execute as long as its condition evaluates to true. It is ideal for binary search where the exact number of iterations is unknown.

Core Code Examples & Terminology

• Algorithm: A finite sequence of well-defined, computer-implementable instructions to solve a class of problems or to perform a computation.

• Sequential Search: An algorithm that checks each element of a list in order until the desired value is found or all elements have been checked. It does not require the data to be sorted.

• Binary Search: An efficient algorithm for finding an item from a sorted list of items. It works by repeatedly dividing in half the portion of the list that could contain the item.

• Precondition: A condition that must be true before a piece of code (like a method) is executed for it to work correctly. For binary search, the precondition is that the array is sorted.

• Core Snippet 1 (Sequential Search):

  
  for (int i = 0; i < arr.length; i++) {
  
      if (arr[i] == target) {
  
          return i;
  
      }
  
  }
  
  return -1;
  

  This loop structure forms the basis of a sequential search, checking every element from start to finish.

• Core Snippet 2 (Binary Search):

  
  int low = 0, high = arr.length - 1;
  
  while (low <= high) {
  
      int mid = low + (high - low) / 2;
  
      if (arr[mid] == target) return mid;
  
      else if (target < arr[mid]) high = mid - 1;
  
      else low = mid + 1;
  
  }
  
  return -1;
  

  This while loop implements the "divide and conquer" logic of a binary search on a sorted array.

Core Skill Check

• Code Tracing: What is the value of mid during the first iteration of a binary search on the array int[] data = {10, 20, 30, 40, 50, 60, 70, 80, 90};?

  Answer: 4

• Debugging: Identify the logical error in this binary search code snippet that will cause an infinite loop if the target is not found.

  
  // ... inside the while loop ...
  
  else if (target < arr[mid]) {
  
      high = mid; // Error is here
  
  } else {
  
      low = mid;  // And here
  
  }
  

  Answer: high should be set to mid - 1 and low to mid + 1 to ensure the search interval shrinks and the loop eventually terminates.

• Application: Write a single line of Java code that correctly updates the high index variable during a binary search if the target is less than the element at the mid index.

  Answer: high = mid - 1;

Common Misconceptions & Errors

• Applying Binary Search on Unsorted Data: Binary search will fail silently, returning an incorrect index or -1 even if the element exists. It absolutely requires the array to be sorted first.

• Off-by-One Loop Condition: Using while (low < high) in a binary search can fail to check the last remaining element. The correct condition is while (low <= high).

• Incorrectly Updating Boundaries: Forgetting to add or subtract 1 when updating low or high (e.g., low = mid; instead of low = mid + 1;) can lead to an infinite loop if the target is not found.

• Forgetting the "Not Found" Case: A search algorithm must handle the case where the target value is not in the array. This is typically done by returning a special value like -1.

Summary

Searching is a core operation in computer science for locating data within a collection. The sequential search provides a simple, universal method that works on any array by checking elements one by one. While easy to implement, its performance degrades on large datasets. In contrast, the binary search offers a highly efficient "divide and conquer" strategy, but it can only be used on data that has been sorted. The choice between them is a classic trade-off: sequential search offers flexibility, while binary search provides superior speed at the cost of requiring sorted data.