Recursive Linear Search A. Iterative Linear Search (given) B. Recursive Linear S
ID: 3565754 • Letter: R
Question
Recursive Linear Search
A. Iterative Linear Search (given)
B. Recursive Linear Search
C. Iterative Binary Search
D. Recursive Binary Search
Download the starting point here.
Turn in the final source and output that does the following:
Recursive Linear Search
File IntegerList.java contains a class IntegerList that represents a list of integers (you may have used a version of this in an earlier lab); IntegerListTest.javacontains a simple menu-driven test program that lets the user create, sort, and print a list and search for an element using a linear search.
Many list processing tasks, including searching, can be done recursively. The base case typically involves doing something with a limited number of elements in the list (say the first element), then the recursive step involves doing the task on the rest of the list. Think about how linear search can be viewed recursively; if you are looking for an item in a list starting at index i:
Fill in the body of the method linearSearchR in the IntegerList class. The method should do a recursive linear search of a list starting with a given index (parameterlo). Note that the IntegerList class contains another method linearSearchRec that does nothing but call your method (linearSearchR). This is done because the recursive method (linearSearchR) needs more information (the index to start at) than you want to pass to the top-level search routine (linearSearchRec), which just needs the thing to look for.
THIS IS THE STARTING CODE
// ****************************************************************
// IntegerList.java
//
// Defines an IntegerList class with methods to create, fill,
// sort, and search in a list of integers. (Version S -
// for use in the linear search exercise.)
//
// ****************************************************************
public class IntegerList
{
int[] list; //values in the list
// ------------------------------------
// Creates a list of the given size
// ------------------------------------
public IntegerList (int size)
{
list = new int[size];
}
// --------------------------------------------------------------
// Fills the array with integers between 1 and 100, inclusive
// --------------------------------------------------------------
public void randomize()
{
for (int i=0; i< list.length; i++)
list[i] = (int)(Math.random() * 100) + 1;
}
// ----------------------------------------
// Prints array elements with indices
// ----------------------------------------
public void print()
{
for (int i=0; i
System.out.println(i + ": " + list[i]);
}
// ------------------------------------------------------------------
// Returns the index of the first occurrence of target in the list.
// Returns -1 if target does not appear in the list.
// ------------------------------------------------------------------
public int linearSearch(int target)
{
int location = -1;
for (int i=0; i
if (list[i] == target)
location = i;
return location;
}
// -----------------------------------------------------------------
// Returns the index of an occurrence of target in the list, -1
// if target does not appear in the list.
// -----------------------------------------------------------------
public int linearSearchRec(int target)
{
return linearSearchR (target, 0);
}
// -----------------------------------------------------------------
// Recursive implementation of the linear search - searches
// for target starting at index lo.
// -----------------------------------------------------------------
private int linearSearchR (int target, int lo)
{
// fill in code for linear search recursive
return -1;
}
// ------------------------------------------------------------------
// Returns the index of the occurrence of target in the list.
// Returns -1 if target does not appear in the list.
// ------------------------------------------------------------------
public int binarySearch(int target)
{
// fill in code for iterative binary search
}
// -----------------------------------------------------------------
// Returns the index of an occurrence of target in the list, -1
// if target does not appear in the list.
// -----------------------------------------------------------------
public int binarySearchRec(int target)
{
return binarySearchR (target, 0, list.length-1);
}
// -----------------------------------------------------------------
// Recursive implementation of the binary search algorithm.
// If the list is sorted the index of an occurrence of the
// target is returned (or -1 if the target is not in the list).
// -----------------------------------------------------------------
private int binarySearchR (int target, int lo, int hi)
{
int index;
// fill in code for the binary search recursive
return index;
}
// ------------------------------------------------------------------------
// Sorts the list into ascending order using the selection sort algorithm.
// ------------------------------------------------------------------------
public void selectionSort()
{
int minIndex;
for (int i=0; i < list.length-1; i++)
{
//find smallest element in list starting at location i
minIndex = i;
for (int j = i+1; j < list.length; j++)
if (list[j] < list[minIndex])
minIndex = j;
//swap list[i] with smallest element
int temp = list[i];
list[i] = list[minIndex];
list[minIndex] = temp;
}
}
}
// ****************************************************************
// IntegerListSTest.java
//
// Provide a menu-driven tester for the IntegerList class.
// (Version S - for use in the linear search lab exercise).
//
// ****************************************************************
import java.util.Scanner;
public class IntegerListTest
{
static IntegerList list = new IntegerList(10);
static Scanner scan = new Scanner(System.in);
// ------------------------------------------------------------------
// Creates a list, then repeatedly print the menu and do what the
// user asks until they quit.
// ------------------------------------------------------------------
public static void main(String[] args)
{
printMenu();
int choice = scan.nextInt();
while (choice != 0)
{
dispatch(choice);
printMenu();
choice = scan.nextInt();
}
}
// -------------------------------------
// Does what the menu item calls for.
// -------------------------------------
public static void dispatch(int choice)
{
int loc;
switch(choice)
{
case 0:
System.out.println("Bye!");
break;
case 1:
System.out.println("How big should the list be?");
int size = scan.nextInt();
list = new IntegerListS(size);
list.randomize();
break;
case 2:
list.selectionSort();
break;
case 3:
System.out.print("Enter the value to look for: ");
loc = list.linearSearch(scan.nextInt());
if (loc != -1)
System.out.println("Found at location " + loc);
else
System.out.println("Not in list");
break;
case 4:
list.print();
break;
//add case 5 and 6 and 7
default:
System.out.println("Sorry, invalid choice");
}
}
// -------------------------------------
// Prints the menu of user's choices.
// -------------------------------------
public static void printMenu()
{
System.out.println(" Menu ");
System.out.println(" ====");
System.out.println("0: Quit");
System.out.println("1: Create new list elements (** do this first!! **)");
System.out.println("2: Sort the list using selection sort");
System.out.println("3: Find an element in the list using linear search");
System.out.println("4: Print the list");
System.out.print(" Enter your choice: ");
}
}
Recursive Binary Search
The binary search algorithm from Chapter 9 is a very efficient algorithm for searching an ordered list. The algorithm (in pseudocode) is as follows:
highIndex - the maximum index of the part of the list being searched
lowIndex - the minimum index of the part of the list being searched
target -- the item being searched for
//look in the middle
middleIndex = (highIndex + lowIndex) / 2
if the list element at the middleIndex is the target
return the middleIndex
else
if the list element in the middle is greater than the target
search the first half of the list
else
search the second half of the list
Notice the recursive nature of the algorithm. It is easily implemented recursively. Note that three parameters are neededthe target and the indices of the first and last elements in the part of the list to be searched. To "search the first half of the list" the algorithm must be called with the high and low index parameters representing the first half of the list. Similarly, to search the second half the algorithm must be called with the high and low index parameters representing the second half of the list. The file IntegerListB.java contains a class representing a list of integers (the same class that has been used in a few other labs); the fileIntegerListBTest.javacontains a simple menu-driven test program that lets the user create, sort, and print a list and search for an item in the list using a linear search or a binary search. Your job is to complete the binary search algorithm (method binarySearchR). The basic algorithm is given above but it leaves out one thing: what happens if the target is not in the list? What condition will let the program know that the target has not been found? If the low and high indices are changed each time so that the middle item is NOT examined again (see the diagram of indices below) then the list is guaranteed to shrink each time and the indices "cross"that is, the high index becomes less than the low index. That is the condition that indicates the target was not found.
lo middle high
lo middle-1 middle+1 high
^ ^ ^ ^
| | | |
------------- --------------------
first half last half
Fill in the blanks below, then type your code in. Remember when you test the search to first sort the list.
private int binarySearchR (int target, int lo, int hi)
{
int index;
if ( ____________________________ ) // fill in the "not found" condition
index = -1;
else
{
int mid = (lo + hi)/2;
if ( ______________________________ ) // found it!
index = mid;
else if (target < list[mid])
// fill in the recursive call to search the first half
// of the list
index = _______________________________________________;
else
// search the last half of the list
index = _______________________________________________;
}
return index;
}
Explanation / Answer
This may help you:
Linear Search Complexity in Java
Linear Search iterate over each element until it found the right element hence it has a variable best case and a fixed average and worst case complexity of 'O(n)'.
Binary Search Implementation in Java
Binary search is more efficient and merely used search algorithm in java programming. To implement Binary search we must have an sorted array or collection. Binary Search searches element in middle of the Array. The array is than divided into sub-array in each iteration accordingly, if the element is greater than the middle element or smaller than the middle element the respective sub-array is used for further searching. Here is a simple Java Program demonstrating binary search in Java.
view plainprint?
Binary Search Complexity in Java
Binary Search divided the search space into half in each iteration and hence has a 'O(log n)' complexity.
Implementation Class Code
This is a simple java class to demonstrate the actual implementation.
view plainprint?
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.