Java/ Data structures. Problem 1 Implement a binary search of an array iterative

Question

Java/ Data structures.

Problem 1

Implement a binary search of an array iteratively using the method

public static > boolean inArrayIterativeSorted(T[] anArray, T anEntry)

Problem 2

Consider an array data of n numerical values in sorted order and a list of numerical target values (target values are not necessarily sorted). Your goal is to compute the smallest range of array indices that contains all of the target values. If a target value is smaller than data[0], the range should start with -1. If a target value is larger than data[n - 1], the range should end with n.

For example, given the array [ 5 8 10 13 15 20 22 26] and the target values (8, 2, 9, 17), the range is -1 to 5.

Devise an efficient algorithm that solves this problem and implement it in

public static >

                                    Interval findInterval(T[] sortedData, List targetValues)

where Interval is a class that provides two public methods getLower() and getUpper() to return the lower and upper values of an Interval object. Implement the Interval class.

If you have n data values in the array and m target values in the list, what is the Big Oh performance of your algorithm?

using java file below to add code

ArraySearcher.java

/**
A class of static methods for searching an array of Comparable objects.

@author Frank M. Carrano
@author Timothy M. Henry
@version 4.0
*/
public class ArraySearcher
{
// Segment 18.3
/** Searches an unsorted array for anEntry. */
public static boolean inArrayIterativeUnsorted(T[] anArray, T anEntry)
{
boolean found = false;
int index = 0;
  
while (!found && (index < anArray.length))
{
if (anEntry.equals(anArray[index]))
found = true;
index++;
} // end while
  
return found;
} // end inArrayIterativeUnsorted
// ========================================================================================

// Segment 18.6
/** Searches an unsorted array for anEntry. */
public static boolean inArrayRecursiveUnsorted(T[] anArray, T anEntry)
{
return search(anArray, 0, anArray.length - 1, anEntry);
} // end inArrayRecursiveUnsorted

// Searches anArray[first] through anArray[last] for desiredItem.
// first >= 0 and < anArray.length.
// last >= 0 and < anArray.length.
private static boolean search(T[] anArray, int first, int last, T desiredItem)
{
boolean found = false;
  
if (first > last)
found = false; // No elements to search
else if (desiredItem.equals(anArray[first]))
found = true;
else
found = search(anArray, first + 1, last, desiredItem);
  
return found;
} // end search
// ========================================================================================

/** Searches a sorted array for anEntry. */
public static > boolean inArrayRecursiveSorted(T[] anArray, T anEntry)
{
return binarySearch(anArray, 0, anArray.length - 1, anEntry);
} // end inArrayRecursiveSorted

// Segment 18.13
// Searches anArray[first] through anArray[last] for desiredItem.
// first >= 0 and < anArray.length.
// last >= 0 and < anArray.length.
private static >
boolean binarySearch(T[] anArray, int first, int last, T desiredItem)
{
boolean found;
int mid = first + (last - first) / 2;
  
if (first > last)
found = false;
else if (desiredItem.equals(anArray[mid]))
found = true;
else if (desiredItem.compareTo(anArray[mid]) < 0)
found = binarySearch(anArray, first, mid - 1, desiredItem);
else
found = binarySearch(anArray, mid + 1, last, desiredItem);

return found;
} // end binarySearch
// ========================================================================================

public static void display(T[] anArray)
{
System.out.print("The array contains the following entries: ");
for (int index = 0; index < anArray.length; index++)
{
System.out.print(anArray[index] + " ");
} // end for
  
System.out.println();
} // end display
} // end ArraySearcher

ArraySort.java

import java.util.* ;
public class SortArray
{
public static <T extends Comparable<? super T>> void selectionSort(T[] a, int n) {
   for (int index = 0; index < n - 1; index++)
   {
       int indexOfSmallest = indexOfSmallest(a, index, n - 1);
       T temp = a[index];
       a[index] = a[indexOfSmallest];
       a[indexOfSmallest] = temp;
       //Invariant: a[0] <= a[1] <= . . . <= a[index] <= all other a[i]
   } // end for
} // end selectionSort
  
private static <T extends Comparable<? super T>>
           int indexOfSmallest(T[] a, int first, int last) {
   T min = a[first];
   int indexOfMin = first;
   for (int index = first + 1; index <= last; index++)
   {
       if (a[index].compareTo(min) < 0)
       {
           min = a[index];
           indexOfMin = index;
}
   }
   return indexOfMin;
}

public static <T extends Comparable<? super T>>
           void insertionSort(T[] a, int n) {
   for(int unsorted = 1; unsorted < n; ++unsorted) {
   T item = a[unsorted];
   int loc = unsorted;
   while(loc > 0 && a[loc-1].compareTo(item) > 0) {
       a[loc] = a[loc-1];
       --loc;
   }
   a[loc] = item;
   }  
}

public static <T extends Comparable<? super T>>
           void bubbleSort(T[] a, int n) {
  
   for(int pass = 1; pass < n ; ++pass) {
   for(int index = 0; index < n-pass; ++index) {
       int nextIndex = index + 1;
       if(a[index].compareTo(a[nextIndex]) > 0) {
       T temp = a[index];
       a[index] = a[nextIndex];
       a[nextIndex] = temp;
       }
   }
   }     
}

public static <T extends Comparable<? super T>>
           void bubbleSort2(T[] a, int n) {
   boolean sorted = false;
   for(int pass = 1; pass < n && !sorted ; ++pass) {
   sorted = true;
   for(int index = 0; index < n-pass; ++index) {
       int nextIndex = index + 1;
       if(a[index].compareTo(a[nextIndex]) > 0) {
       T temp = a[index];
       a[index] = a[nextIndex];
       a[nextIndex] = temp;
       sorted = false;
       }
   }
   }     
}
  
public static void main(String [] args) {
   Integer [] a = { 15, 8 , 10 , 2, 5 };
   //selectionSort(a, a.length);
   //insertionSort(a, a.length);
   //bubbleSort(a, a.length);
   bubbleSort2(a, a.length);
   System.out.println("a = " + Arrays.toString(a));
}
  
} // end SortArray

Explanation / Answer

Implemented functions make them as bold

import java.util.Collection;
import java.util.Collections;
import java.util.List;

/**
*
* @author paramesh
*/
public class ArraySearcher {

/**
* Searches an unsorted array for anEntry.
*/
public static <T> boolean inArrayIterativeUnsorted(T[] anArray, T anEntry) {
boolean found = false;
int index = 0;

while (!found && (index < anArray.length)) {
if (anEntry.equals(anArray[index])) {
found = true;
}
index++;
} // end while

return found;
}

/**
* Searches an unsorted array for anEntry.
*/
public static <T> boolean inArrayRecursiveUnsorted(T[] anArray, T anEntry) {
return search(anArray, 0, anArray.length - 1, anEntry);
} // end inArrayRecursiveUnsorted

// Searches anArray[first] through anArray[last] for desiredItem.
// first >= 0 and < anArray.length.
// last >= 0 and < anArray.length.
private static <T> boolean search(T[] anArray, int first, int last, T desiredItem) {
boolean found = false;

if (first > last) {
found = false; // No elements to search
} else if (desiredItem.equals(anArray[first])) {
found = true;
} else {
found = search(anArray, first + 1, last, desiredItem);
}

return found;
} // end search
// ========================================================================================

/**
* Searches a sorted array for anEntry.
*/
public static <T> boolean inArrayRecursiveSorted(T[] anArray, T anEntry) {
return binarySearch(anArray, 0, anArray.length - 1, anEntry);
} // end inArrayRecursiveSorted

//problem 1

public static <T> boolean inArrayIterativeSorted(T[] anArray, T anEntry) {
int first = 0, last = anArray.length-1;
int mid = first + (last - first) / 2;
while (first <= first) {
mid = (first + last) / 2;
if (anEntry.compareTo(anArray[mid]) < 0) {
last = mid - 1;
} else if (anEntry.compareTo(anArray[mid]) > 0) {
first = mid + 1;
} else {
return true;
}
}
return false;
}
//problem 2
public static <T> void findInterval(T[] sortedData, List targetValues){
T low = null;
T highest = sortedData[0];
// sorting targetValues
Collections.sort(targetValues);
if(targetValues.get(0) == sortedData[0]){
low = sortedData[0];
}
for(int i=0;i<targetValues.size();i++){
for(int j=0;j<sortedData.length;j++){
if(targetValues.get(i) > sortedData[j]){
highest = sortedData[j];
}
}
}
System.out.println("Interval: ["+low+","+ highest+"]");
}
// Segment 18.13
// Searches anArray[first] through anArray[last] for desiredItem.
// first >= 0 and < anArray.length.
// last >= 0 and < anArray.length.

private static <T> boolean binarySearch(T[] anArray, int first, int last, T desiredItem) {
boolean found;
int mid = first + (last - first) / 2;

if (first > last) {
found = false;
} else if (desiredItem.equals(anArray[mid])) {
found = true;
} else if (desiredItem.compareTo(anArray[mid]) < 0) {
found = binarySearch(anArray, first, mid - 1, desiredItem);
} else {
found = binarySearch(anArray, mid + 1, last, desiredItem);
}
return found;
} // end binarySearch
// ========================================================================================

public static <T> void display(T[] anArray) {
System.out.print("The array contains the following entries: ");
for (int index = 0; index < anArray.length; index++) {
System.out.print(anArray[index] + " ");
} // end for

System.out.println();
} // end display
} // end ArraySearcher

Related Questions

Navigate

• Browse (All)
• Browse J
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.