Linear versus binary searching algorithms
When it comes to lists, linear search is pretty straightforward. Essentially you start at the beginning of the list, and check to see if the first item is the item you’re looking for. If it is, you’re done! If it isn’t, you move to the next item in the list. And you repeat this sequence until you’ve either found your item, or you’ve reached the end of the list and know that your item isn’t in the list.Binary searching is a little more complicated than linear searching. Luckily, you’ve probably already used the binary search algorithm in your everyday life though. For example, when you’re looking for the word “Search” in a dictionary, you probably don’t read each word in order until you get to the word “Search.”
Instead, you flip to the middle of the dictionary and check to see whether the word “Search” comes before the page you opened, or after. You know this because the dictionary is in alphabetical order! If “Search” comes after the page you’re on, you flip to a page to the right and repeat the process until you end up on the right page.
This is called binary search, also known as “divide and conquer.” When writing the code for this type of search, you literally go to the middle of the list, and then the middle of the side that you know the word is on; each time dividing your search space by half. In your everyday life you might not be exactly at half, but it’s close enough to still call it a binary search.
The only caveat to binary search is that the list must be sorted for the sorting to work. A linear search implementation doesn’t require your list to be sorted before searching.
Common application: Finding a phone number
Here, you find the code for finding a phone number in a list of names that are ordered alphabetically. This code is written in Java and, because the names are sorted but the phone numbers are not, this implementation uses the linear search algorithm.import java.util.ArrayList; import java.util.Arrays; import java.util.List; import java.util.Scanner;This code relies on another class in a file called Person.java. The code for this file is:public class sort2 { public static void main(String [] args) { Person sarah = new Person("Sarah", "555-7765"); Person camille = new Person("Camille", "555-9834"); Person steve = new Person("Steve", "555-2346"); Person rebecca = new Person("Rebecca", "555-1268");
List directory = Arrays.asList(sarah, camille, steve, rebecca);
Scanner scanner = new Scanner(System.in);
System.out.println("Please enter the phone number so I can tell you the name: ");
String number = scanner.nextLine(); String nameFound = "";
for(int index = 0; index < directory.size(); index++) { Person personInDirectory = directory.get(index);
String numberInDirectory = personInDirectory.getNumber();
if(numberInDirectory.equals(number)) { nameFound = personInDirectory.getName(); break; } }
if(nameFound.equals("")) { System.out.println("Sorry, the number you are looking for does not belong to anyone in this directory"); } else { System.out.println("The number " + number + " belongs to " + nameFound); } } }
public class Person
{
String name;
String number; public Person(String p_name, String p_number)
{
name = p_name;
number = p_number;
}
public String getName()
{
return name;
}
public String getNumber()
{
return number;
}
}