- Binary and Linear Search
- Now lets look at an example of Linear Search
- Now lets look at an example of Binary Search
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
- Remember iteration and selection? Its the same for ArrayLists: a for loop with an if statement inside.
- The for loop parameter uses comparison operators to compare an item inside the ArrayList to the desired searched value
- Keep repeating 1 and 2 until we find the desired searched value
Binary Search
Search Process
- Before anything, the ArrayList HAS to be sorted
- Set the initial minimum, middle, and max of the ArrayList. Your target value is the value you want to find
- 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?
Each hop represents the increment in the for loop.
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;
// Create a list of video games
ArrayList<String> videoGames = new ArrayList<String>();
videoGames.add("Roblox");
videoGames.add("Fortnite");
videoGames.add("Valorant");
videoGames.add("Apex Legends");
videoGames.add("GTA V");
// Price for GTA V (if found)
double gtaVPrice = 29.99; // Example price
// Searching for "GTA V"
String gameToFind = "Grand Theft Auto V";
boolean found = false;
// Linear search
for (String game : videoGames) {
if (game.equalsIgnoreCase(gameToFind)) {
found = true;
break;
}
}
if (found) {
System.out.println("Yes, we have " + gameToFind + " available for $" + gtaVPrice);
} else {
System.out.println("Sorry, " + gameToFind + " is not available. You can find it at a local retailer or online at a major gaming store.");
}
Sorry, Grand Theft Auto V is not available. You can find it at a local retailer or online at a major gaming store.