7.5 Searching

• 7.5 Searching
  • Learning Objectives
  • Essential Knowledge:
  • Search Process
  • Searching Linear Structures
    • Finding information with a computer is something we need to know how to do. Linear search algorithms are BEST used when we do not have any idea about the order of the data and so we need to look at each element to determine if what we are looking for is in fact inside the array or ArrayList.
    • When searching, we do need to remember that different data types require comparisons!
• Searching an ArrayList for an integer
  • Explanation
• Searching an ArrayList of video games for a String
  • Explanation
• Popcorn Hack
  • How do you add an element to an ArrayList?
  • How do you retrieve an element from an ArrayList at a specific index?

Why does order sometimes matter?

• When searching for a value to remove from a list, if we search forward we have to make sure to adjust the loop control variable, or we might skip what we are looking for when removing!

7.5 Searching

Learning Objectives

• Apply sequential/linear search algorithms to search for specific information in array or arraylist objects

Essential Knowledge:

• Sequential/linear search alogorithms check each element in order untill the desired value is found or all elementsin the array or arraylist have been checked

Search Process

• The process of searching a structure incorporates control structures we have used before: iteration and selection AKA a loop with an if inside.

• Inside the for loop, we retrieve the value from the structure at the specified index and compare it to the searched value

• If it matches we return the index, otherwise we keep looking!

Searching Linear Structures

Finding information with a computer is something we need to know how to do. Linear search algorithms are BEST used when we do not have any idea about the order of the data and so we need to look at each element to determine if what we are looking for is in fact inside the array or ArrayList.

When searching, we do need to remember that different data types require comparisons!

• When looking at int values, the == operator is the tool to use!
• When searching for a double value, we need to make sure the value is close enough by doing some math!

• Object instances should always use the .equals(otheThing) method to check for a match!

• When searching a linear structure we need to send it the structure and what we are looking for as parameters Usually, the search method will return the index of the found item or -1 if it is not found. We can also simply return a boolean value if the desired item is located anywhere inside the structure.
• A standard for loop with an if block is all we need to search any linear structure. If the item matches the condition, it should return the index immediately so we don’t need to continue executing the method.
• If the value is not found after completing the loop it can return -1 indicating there is no index with the desired value.

Searching an ArrayList for an integer

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

public class Main {
    public static void main(String[] args) {
        ArrayList<Integer> numbers = new ArrayList<Integer>();
        numbers.add(1);
        numbers.add(2);
   
        numbers.add(4);
        numbers.add(5);
       
        numbers.add(7);
        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++ ) {
            if (numbers.get(index) == desiredNumber) {

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

        
    }   

}

Explanation

Create the ArrayList of numbers and then add numbers. Create a Scanner object which asks for user’s desired number Uses a for loop to iterate through each number in the ArrayList Conditional if statement to check if the user’s desired number is in the list

Searching an ArrayList of video games for a String

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

public class searchString {
    public static void main(String[] args) {
        ArrayList<String> videoGames = new ArrayList<String>();
        videoGames.add("Valorant");
        videoGames.add("Fortnite");
        videoGames.add("Brawl Stars");
        videoGames.add("Apex Legends");
        videoGames.add("CS-GO");
        videoGames.add("Rust");
        
        Scanner scanGame = new Scanner(System.in);
        System.out.println("Enter your favorite video game: ");
        String desiredGame = scanGame.nextLine();


        for (String game: videoGames) {
            if (game.equalsIgnoreCase(desiredGame)) {
                System.out.println(desiredGame + "is in the list.");
                scanGame.close();
            } else {
                System.out.println(desiredGame + "is not in the list.");
                scanGame.close();
            }
        }

    }

}

Explanation

Create the ArrayList of videoGames and then add items. Create a Scanner object which asks for user’s desired number Uses a for loop to iterate through each game in the ArrayList Conditional if statement to check if the user’s favorite game is in the list

Popcorn Hack

How do you add an element to an ArrayList?

list.add(element)

How do you retrieve an element from an ArrayList at a specific index?

list.contains(element)

• These are all methods unique to ArrayLists

Why does order sometimes matter?

When searching for a value to remove from a list, if we search forward we have to make sure to adjust the loop control variable, or we might skip what we are looking for when removing!