CSE1322-Lab 1B Search Solved

Write programs in Java to search a 1 dimensional array using a linear search and a binary search.
For this lab, you should work alone.  You will use Eclipse as your IDE.

Directions

This lab has two parts:

1.  Writing a simple linear search application

2.  Writing a simple binary search application

Part 1 – Linear Search

Background: Remember that the linear search will compare all elements of an array with a supplied “key” value for a positive match.  On average, the algorithm will have to compare half the elements in the array before finding a match, if it exists.  Think about how much time is increased for every element you add to an array.  Is the linear search efficient?

First, you'll need to create a project.  

1.     Start Eclipse.  It may ask you if you want the default language to be Java, C, C++, Python.  If it does, just choose Java.

Go to the File menu and select New - Java
Notice that you have a choice of languages.  Let's choose a Java project
Change the directory location to something "safe".  You may want to temporarily choose the Desktop and then save the file to something permanent once you're done (e.g. flash drive). 
You should now see an open file. 
Put your name as a comment on the top of the class.
Write the name of the class, perhaps Lab2ALinear
Write the main method header 
Add a new java class to your existing folder.
Put your name as a comment on the top of the class.
You will be generating random numbers so import java.util.Random.
You should consider developing the methods for this project incrementally.  
9.     In main, use an initializer list create an array of ints called nums holding the following values:  1, 4, 4, 22, -5, 10, 21, -47, 23

10.  Write a method, called linearSearch, that returns the index of the key element if found in the array, otherwise it will return a -1

11.  Create an int array of size 20, called data and write a method to fill the array with random ints [-100, 100].  Recall that random’s nextInt( x) method returns a value from 0 to x-1.  The upper bound is exclusive.  Modify the values to fit the required ranges.

12.  Use the linearSearch method you previously wrote to return the index of the key value searched for in data for the client to print

13.  Print the value of the key value search for and the index of the value, if found, or the phrase “Value not found in the array”, if not found.  

 

Part 2 – Binary Search

Background: The binary search must be performed on an array that is sorted in order.  The binary search starts by comparing the key to the value in the middle of the array.  There are three cases: 

-        The key is less than the middle element, then you need only search the lower half of the array.

-        The key is equal to the middle element, then your search is over.

-        The key is greater than the middle element, then you need only search the upper half of the array. 

First, you'll need to create a project.  

2.     Start Eclipse.  It may ask you if you want the default language to be Java, C, C++, Python.  If it does, just choose Java.

Go to the File menu and select New - Java
Notice that you have a choice of languages.  Let's choose a Java project
Change the directory location to something "safe".  You may want to temporarily choose the Desktop and then save the file to something permanent once you're done (e.g. flash drive). 
You should now see an open file. 
Put your name as a comment on the top of the class.
Write the name of the class, perhaps Lab2BBinary
Write the main method header 
Add a new java class to your existing folder.
Put your name as a comment on the top of the class.
You will be generating random numbers so import java.util.Random.
You should consider developing the methods for this project incrementally.  
21.  In main, use an initializer list create an array of ints called nums holding the following values:  1, 4, 4, 22, -5, 10, 21, -47, 23

22.  Write a method, called binarySearch, that returns the index of the key element if found in the array, otherwise it will return the value of minus(insertion point +1).  Ex. Given the array values in #21 above, the array will be sorted as -47,-5,1,4,4,10,21,22,23.  The index for key of 4 will be 3.  The return value when search for 6 will be the insertion point for 6 which is index of 5, so the return will be minus(5+1) = -6.

23.  Create an int array of size 20, called data and write a method to fill the array with random ints [-100, 100].  Recall that random’s nextInt( x) method returns a value from 0 to x-1.  The upper bound is exclusive.  Modify the values to fit the required ranges.

24.  Use the binarySearch method you previously wrote to return the index of the key value searched for in data for the client to print

25.  Print the value of the key value search for and the index of the value, or the value of 

–(insertion point +1)