My recursive methods for binary search and sequential search don\'t work properl
ID: 3539212 • Letter: M
Question
My recursive methods for binary search and sequential search don't work properly they are not able to find the numbers in the array . please help... ONLY MY RECURSIVE BINARY AND SEQUENTIAL
public interface SearchSortADT<T>
{
public int seqSearch(T[] list, int length, T searchItem);
//Sequential search algorithm.
//Postcondition: If searchItem is found in the list,
// it returns the location of searchItem;
// otherwise it returns -1.
public int binarySearch(T[] list, int length, T searchItem);
//Binary search algorithm.
//Precondition: The list must be sorted.
//Postcondition: If searchItem is found in the list,
// it returns the location of searchItem;
// otherwise it returns -1.
public void bubbleSort(T list[], int length);
//Bubble sort algorithm.
//Postcondition: list objects are in ascending order.
public void selectionSort(T[] list, int length);
//Selection sort algorithm.
//Postcondition: list objects are in ascending order.
public void insertionSort(T[] list, int length);
//Insertion sort algorithm.
//Postcondition: list objects are in ascending order.
public void quickSort(T[] list, int length);
//Quick sort algorithm.
//Postcondition: list objects are in ascending order.
public void heapSort(T[] list, int length);
//Heap sort algorithm.
//Postcondition: list objects are in ascending order.
public void Rbinarysearch(T[] list,int first, int upto, int searchItem);
//Recursive Binary Search
public void RecursiveSequentialSearch(T[] list,int first, int upto, int searchItem);
}
_____________________________________________________________________
import java.io.PrintStream;
public class SearchSortAlgorithms<T> implements SearchSortADT<T> {
// Sequential search algorithm.
// Postcondition: If searchItem is found in the list,
// it returns the location of searchItem;
// otherwise it returns -1.
public int seqSearch(T[] list, int length, T searchItem) {
int loc;
boolean found = false;
for (loc = 0; loc < length; loc++) {
if (list[loc].equals(searchItem)) {
found = true;
break;
}
}
if (found)
return loc;
else
return -1;
} // end seqSearch
// Binary search algorithm.
// Precondition: The list must be sorted.
// Postcondition: If searchItem is found in the list,
// it returns the location of searchItem;
// otherwise it returns -1.
public int binarySearch(T[] list, int length, T searchItem) {
int first = 0;
int last = length - 1;
int mid = -1;
boolean found = false;
while (first <= last && !found) {
mid = (first + last) / 2;
Comparable<T> compElem = (Comparable<T>) list[mid];
if (compElem.compareTo(searchItem) == 0)
found = true;
else if (compElem.compareTo(searchItem) > 0)
last = mid - 1;
else
first = mid + 1;
}
if (found)
return mid;
else
return -1;
}// end binarySearch
// Bubble sort algorithm.
// Postcondition: list objects are in ascending order.
public void bubbleSort(T list[], int length) {
for (int iteration = 1; iteration < length; iteration++) {
for (int index = 0; index < length - iteration; index++) {
Comparable<T> compElem = (Comparable<T>) list[index];
if (compElem.compareTo(list[index + 1]) > 0) {
T temp = list[index];
list[index] = list[index + 1];
list[index + 1] = temp;
}
}
}
}// end bubble sort
// Selection sort algorithm.
// Postcondition: list objects are in ascending order.
public void selectionSort(T[] list, int length) {
for (int index = 0; index < length - 1; index++) {
int minIndex = minLocation(list, index, length - 1);
swap(list, index, minIndex);
}
}// end selectionSort
// Method to determine the index of the smallest item in
// list between the indices first and last..
// This method is used by the selection sort algorithm.
// Postcondition: Returns the position of the smallest
// item.in the list.
private int minLocation(T[] list, int first, int last) {
int minIndex = first;
for (int loc = first + 1; loc <= last; loc++) {
Comparable<T> compElem = (Comparable<T>) list[loc];
if (compElem.compareTo(list[minIndex]) < 0)
minIndex = loc;
}
return minIndex;
}// end minLocation
// Method to swap the elements of the list speified by
// the parameters first and last..
// This method is used by the algorithms selection sort
// and quick sort..
// Postcondition: list[first] and list[second are
// swapped..
private void swap(T[] list, int first, int second) {
T temp;
temp = list[first];
list[first] = list[second];
list[second] = temp;
}// end swap
// Insertion sort algorithm.
// Postcondition: list objects are in ascending order.
public void insertionSort(T[] list, int length) {
for (int firstOutOfOrder = 1; firstOutOfOrder < length; firstOutOfOrder++) {
Comparable<T> compElem = (Comparable<T>) list[firstOutOfOrder];
if (compElem.compareTo(list[firstOutOfOrder - 1]) < 0) {
Comparable<T> temp = (Comparable<T>) list[firstOutOfOrder];
int location = firstOutOfOrder;
do {
list[location] = list[location - 1];
location--;
} while (location > 0 && temp.compareTo(list[location - 1]) < 0);
list[location] = (T) temp;
}
}
}// end insertionSort
// Quick sort algorithm.
// Postcondition: list objects are in ascending order.
public void quickSort(T[] list, int length) {
recQuickSort(list, 0, length - 1);
}// end quickSort
// Method to partition the list between first and last.
// The pivot is choosen as the middle element of the list.
// This method is used by the recQuickSort method.
// Postcondition: After rearranging the elements,
// according to the pivot, list elements
// between first and pivot location - 1,
// are smaller the the pivot and list
// elements between pivot location + 1 and
// last are greater than or equal to pivot.
// The position of the pivot is also
// returned.
private int partition(T[] list, int first, int last) {
T pivot;
int smallIndex;
swap(list, first, (first + last) / 2);
pivot = list[first];
smallIndex = first;
for (int index = first + 1; index <= last; index++) {
Comparable<T> compElem = (Comparable<T>) list[index];
if (compElem.compareTo(pivot) < 0) {
smallIndex++;
swap(list, smallIndex, index);
}
}
swap(list, first, smallIndex);
return smallIndex;
}// end partition
// Method to sort the elements of list between first
// and last using quick sort algorithm,
// Postcondition: list elements between first and last
// are in ascending order.
private void recQuickSort(T[] list, int first, int last) {
if (first < last) {
int pivotLocation = partition(list, first, last);
recQuickSort(list, first, pivotLocation - 1);
recQuickSort(list, pivotLocation + 1, last);
}
}// end recQuickSort
// Heap sort algorithm.
// Postcondition: list objects are in ascending order.
public void heapSort(T[] list, int length) {
buildHeap(list, length);
for (int lastOutOfOrder = length - 1; lastOutOfOrder >= 0; lastOutOfOrder--) {
T temp = list[lastOutOfOrder];
list[lastOutOfOrder] = list[0];
list[0] = temp;
heapify(list, 0, lastOutOfOrder - 1);
}// end for
}// end heapSort
// Method to the restore the heap in the list between
// low and high.
// This method is used by the heap sort algorithm and
// the method buildHeap.
// Postcondition: list elemets between low and high are
// in a heap.
private void heapify(T[] list, int low, int high) {
int largeIndex;
Comparable<T> temp = (Comparable<T>) list[low]; // copy the root
// node of
// the subtree
largeIndex = 2 * low + 1; // index of the left child
while (largeIndex <= high) {
if (largeIndex < high) {
Comparable<T> compElem = (Comparable<T>) list[largeIndex];
if (compElem.compareTo(list[largeIndex + 1]) < 0)
largeIndex = largeIndex + 1; // index of the
// largest child
}
if (temp.compareTo(list[largeIndex]) > 0) // subtree
// is already in a heap
break;
else {
list[low] = list[largeIndex]; // move the larger
// child to the root
low = largeIndex; // go to the subtree to
// restore the heap
largeIndex = 2 * low + 1;
}
}// end while
list[low] = (T) temp; // insert temp into the tree,
// that is, list
}// end heapify
// Method to convert an array into a heap.
// This method is used by the heap sort algorithm
// Postcondition: list elements are in a heap.
private void buildHeap(T[] list, int length) {
for (int index = length / 2 - 1; index >= 0; index--)
heapify(list, index, length - 1);
}// end buildHeap
/**
* Recursive binary search of sorted array. Negative value on failure. The
* upperbound index is not included in the search. This is to be consistent
* with the way Java in general expresses ranges. The performance is O(log
* N).
*
* @param sorted
* Array of sorted values to be searched.
* @param first
* Index of beginning of range. First element is a[first].
* @param upto
* Last element that is searched is sorted[upto-1].
* @param key
* Value that is being looked for.
* @return Returns index of the first match, or or -insertion_position -1 if
* key is not in the array. This value can easily be transformed
* into the position to insert it.
*/
public int rBinarySearch(T[] list, int first, int upto, T searchItem) {
// a negative integer, zero, or a positive integer as this object is
// less than, equal to, or greater than the specified object.
if (first <= upto) {
int mid = (first + upto) / 2;
Comparable<T> compElem = (Comparable<T>) list[mid];
if (compElem.compareTo(searchItem) > 0)
return rBinarySearch(list, first, mid - 1, searchItem);
if (compElem.compareTo(searchItem) < 0)
return rBinarySearch(list, mid + 1, upto, searchItem);
// if (searchItem < list[mid])
// return rBinarySearch(list, searchItem, first, mid - 1); // search
// a[start]
// to
// a[mid-1]
// else if (searchItem > list[mid])
// return rBinarySearch(list, searchItem, mid + 1, upto); // search
// a[mid+1]
// to
// a[end]
else
return mid; // x found and x = a[mid]
}
return -1;
}
public int RecursiveSequentialSearch(T[] list, int first, int upto,
T searchItem) {
Comparable<T> compElem = (Comparable<T>) list[first];
{
if (first == upto)
{
return -1;
}
else
{
if (compElem.compareTo(searchItem) == 0)
// if (list[first] == searchNum)
{
return (first);
}
else
{
return RecursiveSequentialSearch(list, first + 1, upto, searchItem);
}
}
}
}
}
import java.util.*;
public class Driver {
/**
* @param args
*/
public static void main(String[] args) {
Integer[] intList = { 2, 16, 34, 45, 53, 56, 69, 70, 75, 96 }; // Binary
// Search
Integer[] intList1 = { 16, 2, 14, 69, 45, 3, 56, 70, 96, 75 }; // Sequential
// Search
Integer[] intList2 = { 2, 16, 34, 45, 53, 56, 69, 70, 75, 96 }; // Recursive
// Binary
// Search
Integer[] intList3 = { 2, 89, 14, 23, 45, 3, 43, 70, 96, 4 }; // Recursive Sequential
// Search
SearchSortAlgorithms<Integer> intSearchObject = new SearchSortAlgorithms<Integer>();
// BINARY SEARCH
System.out.println("Binary Search");
print(intList, intList.length);
System.out.println("Please enter a number from the above list: ");
Scanner input = new Scanner(System.in);
int xNumber = input.nextInt();
int pos;
pos = intSearchObject.binarySearch(intList, intList.length, xNumber);
if (pos != -1)
System.out.println(xNumber + " was found at position " + pos
+ " with Binary Search.");
else
System.out.println(xNumber + " was not found in the Array "
+ "with Binary Search.");
System.out.println(" ");
// SEQUENTIAL SEARCH
System.out.println("Sequential Search");
print(intList1, intList1.length);
System.out.println("Please enter a number from the above list: ");
Scanner input1 = new Scanner(System.in);
int yNumber = input1.nextInt();
int posSeq;
posSeq = intSearchObject.seqSearch(intList1, intList1.length, yNumber);
if (posSeq != -1)
System.out.println(yNumber + " was found at position " + posSeq
+ " with Sequential Search.");
else
System.out.println(yNumber + " was not found in the Array "
+ "with Sequential Search.");
System.out.println(" ");
// RECURSIVE BINARY SEARCH
System.out.println(" Recursive Binary Search");
print(intList, intList2.length);
System.out.println("Please enter a number from the above list: ");
Scanner input2 = new Scanner(System.in);
int zNumber = input2.nextInt();
int posRbinary;
posRbinary = intSearchObject.rBinarySearch(intList2, intList2[0],
intList2.length - 1, zNumber);
if (posRbinary != -1)
System.out.println(zNumber + " was found at position " + posRbinary
+ " with Recusive Binary Search.");
else
System.out.println(zNumber + " was not found in the Array "
+ "with Recursive Binary Search.");
System.out.println(" ");
// RECURSIVE SEQUENTIAL SEARCH
System.out.println(" Recursive SEQUENTIAL Search");
print(intList, intList2.length);
System.out.println("Please enter a number from the above list: ");
Scanner input3 = new Scanner(System.in);
int sNumber = input3.nextInt();
int posRSequential;
posRSequential = intSearchObject.RecursiveSequentialSearch(intList3, intList3[0],
intList3.length - 1, sNumber);
if (posRSequential != -1)
System.out.println(sNumber + " was found at position " + posRSequential
+ " with Recursive Sequential Search.");
else
System.out.println(sNumber + " was not found in the Array "
+ "with Recursive Sequential Search.");
System.out.println(" ");
}
public static <T> void print(T[] list, int length) {
for (int i = 0; i < length; i++)
System.out.print(list[i] + " ");
System.out.println();
}
Explanation / Answer
int RlinearSearch(int T[], int n, int searchitem)
{
if (n < 0 )
{
return -1;
}
if(searchitem == T[n-1])
{
return n - 1;
}
linearSearch(T, n-1, searchitem);
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.