7.5 Searching

• Binary and Linear Search
  • Linear(Sequential) Search
  • Binary Search
• Now lets look at an example of Linear Search
  • Code
  • Things to Remember
  • Popcorn Hack #1(0.2 mins)
• Now lets look at an example of Binary Search
  • Code

Binary and Linear Search

There are two search algorithms you will see on the AP exam:

• Linear Search
• Binary Search

Linear(Sequential) Search

Search Process

1. Remember iteration and selection? Its the same for ArrayLists: a for loop with an if statement inside.
2. The for loop parameter uses comparison operators to compare an item inside the ArrayList to the desired searched value
3. Keep repeating 1 and 2 until we find the desired searched value

Binary Search

Search Process

1. Before anything, the ArrayList HAS to be sorted
2. Set the initial minimum, middle, and max of the ArrayList. Your target value is the value you want to find
3. Check middle value in comparison with the minimum and maximum
   • If the middle value is less than the target value, only check the right half of the ArrayList
   • If the middle value is greater than the target value, only check the left half of the ArrayList

Yes its very confusing but just look at the GIF

Now lets look at an example of Linear Search

Visualize this while going through the code

• A for loop will go through each index and its corresponding value until it finds the desired value.

Code

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        ArrayList<Integer> numbers = new ArrayList<Integer>();
        
        // missing 3, 6, 7, and 10
        numbers.add(1);
        numbers.add(2);
        
        numbers.add(4);
        numbers.add(5);
        
      
        numbers.add(8);
        numbers.add(9);
        
        
        Scanner scanNumber = new Scanner(System.in);
        System.out.println("Enter a number 1-10");
        Integer desiredNumber = scanNumber.nextInt();
        

        for (int index = 0; index < numbers.size(); index++) {
            // notice how the == operator is used to compare integers
            if (numbers.get(index) == desiredNumber) {

                System.out.println(desiredNumber + " is in the list");
                scanNumber.close();
            } else {
                System.out.println(desiredNumber + " is not in the list.");
                scanNumber.close();
            }
        }

        
    }   

}

Things to Remember

To remember linear searching, think:

• Iteration and Selection
  • Iteration
    • Iteration is the process of repeating a step multiple times; In this case, we keep searching for a desired value until it is found
  • Selection
    • Selection is the process of finding a specific element within a list. We do this using comparison operators
• When comparing int values, use the == operator.
• When comparing Object values, use the .equals() method to compare values.

Popcorn Hack #1(0.2 mins)

What does each hop or jump represent? What code(look above) is used to achieve this?

Now lets look at an example of Binary Search

Visualize this while going through the code

• Repeatedly divide the search range in half until the target is found or the range is empty
• this is a great GIF to visualize binary searching

Code

import java.util.ArrayList;
import java.util.Collections;


public static int binarySearch(ArrayList<Integer> elements, int target)
{
    // min and max is the RANGE of the ArrayList
    int min = 0;
    int max = elements.size() - 1;

    // while loop will ensure the array continues to be split in half until target is found
    while (min <= max)
    {
        // this middle value is the INDEX not VALUE. 
        int middle = (min + max) / 2;

        // now we check if the middle VALUE is less than the number we want. 
        // *remember* the list is sorted so...
        // if middle is less than the target, you want to split the array into the UPPER HALF
        // if middle is more than the target, you want to split the array into the LOWER HALF
        if (elements.get(middle) < target) { // too low
            min = middle + 1;
        } else if (elements.get(middle) > target) { // too high
            max = middle - 1;
        } else if (elements.get(middle) == target) { // just right
            return middle;
        }
    }

    return -1;
}

ArrayList<Integer> numbers = new ArrayList<>();
numbers.add(-20);
numbers.add(3);
numbers.add(15);
numbers.add(81);
numbers.add(432);

// binary searches HAVE to be sorted
Collections.sort(numbers);


int index = binarySearch(numbers, 15);
System.out.println(index);

index = binarySearch(numbers, -20);
System.out.println(index);

index = binarySearch(numbers, 432);
System.out.println(index);

index = binarySearch(numbers, 53);
System.out.println(index);

2
0
4
-1

Homework

• Imagine you’re an online E-store that sells video games. Use linear searching to help Aidan find if the game, Grand Theft Auto V, is offered in the E-store. If it is, tell him the price. If it isn’t, tell him where he can find it

import java.util.ArrayList;

public class searchString {
    public static void main(String[] args) {
        ArrayList<String> videoGames = new ArrayList<String>();
        videoGames.add("Roblox");
        videoGames.add("Fortnite");
        videoGames.add("Valorant");
        videoGames.add("Apex Legends");
        videoGames.add("GTA V");

        // *code*
}