## 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 dataConsider 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 valueInsert a new item into the listRemove an item from a listSort the listOver 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`

#### 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! ~