Welcome Back!


Learning Objectives for Today's Lesson

By the end of today's lesson, you should know...
  • What are some common actions you might take on an array?
  • What are two methods of searching for an element in an array?
  • How do the approaches of the linear and binary search algorithms differ?
  • Which of the two algorithms is considered to be more efficient?
  • Which algorithm requires a sorted array?

1. Working with Arrays

  • Recall that arrays are simply a means of storing a list of data
  • Consider lists that you make in your day-to-day life: shopping lists, to-do lists, class lists, etc.
  • What are some of the things you might do with your list?
    • Search the list for a specific value
    • Insert a new item into the list
    • Remove an item from a list
    • Sort the list
  • Over the next few lessons, we will discuss how to approach each of the above actions using arrays to store a list of data.
A List of the "Most In-Demand" Programming Languages - Information that can be stored using an array

Searching An Array for a Value

  • Suppose you want to find a particular value in an array
  • This is known as searching an array
  • There are two common approaches to searching an array - linear and binary search

2. Linear Search

  • An easy and straightforward algorithm is linear search (a.k.a. sequential search)
  • In linear search you:
    • Start at the beginning of the list
    • Compare each value in the list looking for matches:
      • If the value is found, then return the location of the value inside the array (index #0...length-1)
      • If you reach the end of the list, return "not found"
  • Since an index must be >= 0, then we can use -1 as the "not found" value


Linear Search Pseudocode:

method linearSearch(A[0 ... n-1], value)
        For each item in the list:
             if that item has the desired value,
                 stop the search and return the item's location.
    //end for loop
    return -1.


Activity 2.1: Linear Search (10 pts)

  • Let's write the code for linear search.
  • In this program, we will use the linear search method to allow a user to search for a programming language to see if it is one of the 20 most popular languages currently used in industry today according to the Tiobe Community Programming Index
  • Open up a new Java project in Eclipse and name it Search with a class named Search.java
  • Copy and paste the starter code into your file.
  • Note that you are provided with an array that is ordered from the #1 most popular language (Java, of course!) to the #20 most popular language.

/**
* @author
* CIS 36B
*/
import java.util.Scanner;

public class Search {

public static void main(String[] args) {
int location;
String[] mostPopular = { "Java", "C", "C++", "Python",
"C#", "PHP", "Javascript", "SQL", "Objective C",
"Swift", "Ruby", "Assembly language", "R", "MATLAB",
"Delphi/Objective Pascual", "Perl", "Go",
"Visual Basic", "PL/SQL", "Scratch" };
System.out.print("Welcome!\n\nEnter the name of a programming language: ");
Scanner input = new Scanner(System.in);
String name = input.nextLine();
//call linear search method here
System.out.println("According to the Tiobe Community Programming "
+ "Index:\n");
if(location == -1) {
System.out.println(name + " is not one of the top "
+ "20 most popular programming languages");
} else {
System.out.println(name + " is language #"
+ (location + 1) + " in the list of 20 most popular"
+ " programming languages");
}

}


/**
* Searches an array sequentially for a particular value
* @param array the array to search
* @param value the value to search for
* @return the index of the item in the array
* if it exists in the array or -1 if it doesn't
*/
//Write linear search method here

} //end of class

  • Now, given the pseudocode for linear search above, write the linearSearch method.
  • Then, call your method inside of main where indicated by the comment.
  • Your program should now work like this:
  • Alternately,
  • Once your program is completed, upload Search.java to Canvas.

3. Binary Search 

  • A different, but "more efficient" (quicker, easier) approach to searching a list of data is an algorithm known as binary search.
  • Conceptually, binary search is similar to the approach we might take to searching for a word in a dictionary or a name in a phone book.
  • We might start in the middle of the book. If the name or word is on that page, then we are in luck and stop searching.
  • Otherwise, if we land in the Ms and our word begins with an R, we know to look in the the second half of the book.
  • If our word begins with an E, we know to look in the first half of the book.
  • We can keep dividing our search space in half until we find the right word.
  • Below is a visual example of Binary Search in action on a sorted array.
  • Binary search will only work on a sorted array.
  • What does it mean to be sorted?
    • For numbers: sorted in either increasing (e.g. 1, 2, 3, ... 10) or decreasing (e.g. 10, 9, 8, ... 1) order
    • For Strings: alphabetical ordering (Unicode)
  • Why does binary search require an array to be sorted?
    • Given an unsorted array, we must use linear search.
Mario performs Binary Search
















Binary Search Pseudocode:

method binarySearch(A[0 ... n - 1], value)
    low = 0
    high = A.length - 1
    while low <= high     mid := (low + high)/2     if A[mid] := value     return mid     else if value < A[mid] //search the left half     high := mid - 1     else //search the right half     low := mid+1
    //end of while loop
    return -1

Binary Search vs Linear Search

https://www.mathwarehouse.com/programming/images/binary-vs-linear-search/binary-and-linear-search-animations.gif

image source

Activity 2.2: Binary Search (10 pts)

  • Let's add to the Search program you wrote previously by adding a binary search fu.
  • However, we are going to need to add a second array to the program, as we cannot call binarySearch on the mostPopular array from the last activity. (Why not?)
  • Open up a the Search.java class from the last activity.
  • Below the mostPopular array declaration, add the declaration for the following array:
String[] mostInDemand = {"C#", "C++", "Java", "Javascript",
                "Perl", "PHP", "Python", "R", "Rust", "Swift"};
  • This array is an alphabetized list of the 10 most in-demand languages of 2018 as projected by Information Week.
  • Now, given the pseudocode for binary search provided above, write the binarySearch method - including its Javadoc comment - below the linearSearch method.
    • Hint: You will need to use the compareTo method for Strings.
  • Next, add the below code to main below the if-else statements from the last activity and above the closing curly brace for main:
        location = //fill in the call to binarySearch here!
    System.out.println("\nAccording to Information Week:\n");
    if(location == -1) {
        System.out.println(name + " is not one of the top "
                    + "10 most in-demand programming languages of 2018");
    } else {
        System.out.println(name + " is one of the most in-demand"
                    + " programming languages of 2018");
    }

  • Add in the call to binarySearch where indicated by the comment.
  • Your program should now work like this:
  • Alternately,

  • Once your program is completed, upload Search.java to Canvas.



Wrap Up

  • Answer the practice exam questions on Canvas.


Upcoming Assignments

  • Lesson 2 Activities due Thursday at 11:59pm on Canvas
  • Lesson 2 Practice Exam Questions due Thursday at 11:59pm on Canvas
  • Quiz 1 due Friday at 11:59pm on Canvas
  • Peer Evaluations for Lesson 1 and Lesson 2 Practice Exam Questions due Saturday at 11:59pm
    • You will be assigned 4 reviews in total to complete
  • Lab 1 due Monday at 11:59pm
~ Have a Great Weekend! ~