P1 (20 points) Implement a binary search of an array iteratively using the metho
ID: 3700072 • Letter: P
Question
P1 (20 points)
Implement a binary search of an array iteratively using the method
public static <T extends Comparable<? super T>> boolean inArrayIterativeSorted(T[] anArray, T anEntry)
P2 (30 points)
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 <T extends Comparable<? super T>>
Interval findInterval(T[] sortedData, List<T> 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?
ArraySearcher.java
/**
A class of static methods for searching an array of Comparable objects.
*/
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
As per the give data wrote a program, as shown below
JAVA PROGRAM:
import java.util.ArrayList;
public class ProblemApp {
public static void main(String[] args){
Integer[] array = {4,5,6,7,9,11,24};
Integer[] arrayscr = {5,4,6,24,11,9,7};
ArrayList<Integer> list = new ArrayList<Integer>();
list.add(3);
list.add(2);
list.add(6);
list.add(4);
list.add(7);
System.out.println(Problem.inArrayIterativeSorted(array, 10));
System.out.println(Problem.inArrayIterativeSorted(array, 9));
System.out.println(Problem.findInterval(array, list).getLower() + ", " + Problem.findInterval(array, list).getUpper());
System.out.println(Problem.isSorted(array));
Problem.modifiedSelectionSort(arrayscr, arrayscr.length);
for(int i = 0; i< array.length; i++){
System.out.print(arrayscr[i] + ", ");
}
}
}
----
import java.util.* ;
public class Problem
{
// Problem 1
public static <T extends Comparable<? super T>>
boolean inArrayIterativeSorted(T[] anArray, T anEntry) {
boolean found = false;
int start = 0;
int end = anArray.length - 1;
while(!found){
int mid = start + (end - start) / 2;
if(anArray[mid].equals(anEntry)){
found = true;
break;
}
else if(anEntry.compareTo(anArray[mid]) > 0){
if(start == end && !anArray[mid].equals(anEntry) ){
break;
}
else{
start = mid + 1;
}
}
else if(anEntry.compareTo(anArray[mid]) < 0){
if(start == end && !anArray[mid].equals(anEntry)){
break;
}
else{
end = mid - 1;
}
}
}
return found;
}
----
public static <T extends Comparable<? super T>>
Interval findInterval(T[] sortedData, List<T> targetValues){
int lower = 0, upper = 0, tempLower = 0, tempUpper = 0;
T min = targetValues.get(0);
int indexOfMin = 0;
for (int index = 1; index < targetValues.size(); index++) {
if (targetValues.get(index).compareTo(min) < 0) {
min = targetValues.get(index);
indexOfMin = index;
}
}
T max = targetValues.get(0);
int indexOfMax = 0;
for (int index = 1; index < targetValues.size(); index++) {
if (targetValues.get(index).compareTo(max) > 0) {
max = targetValues.get(index);
indexOfMax = index;
}
}
if(min.compareTo(sortedData[0]) == -1){
lower = -1;
}
else{
for (int index = 0; index < sortedData.length; index++) {
if (sortedData[index].compareTo(min) == -1) {
lower = index - 1;
break;
}
}
}
for (int index = 0; index < sortedData.length; index++) {
if (sortedData[index].compareTo(max) == 1) {
upper = index + 1;
break;
}
}
Interval result = new Interval(lower,upper);
return result;
}
--
public static <T extends Comparable<? super T>> boolean isSorted(T[ ] a) {
boolean result = false;
int iterator = 0;
while(iterator < a.length - 1){
if(a[iterator].compareTo(a[iterator+1]) < 1){
result = true;
}
else{
result = false;
break;
}
iterator++;
}
return result;
}
--
public static <T extends Comparable<? super T>> void modifiedSelectionSort(T[] a, int n) {
for(int i = 0; i < n-1; i++){
T min = a[i];
int indexOfMin = 0;
for (int index = i; index <= n - 1; index++) {
if (a[index].compareTo(min) < 0) {
min = a[index];
indexOfMin = index;
}
}
if(indexOfMin == 0){
continue;
}
else{
T temp = a[i];
a[i] = a[indexOfMin];
a[indexOfMin] = temp;
}
}
for(int i = n; i < 1; i--){
T max = a[n-1];
int indexOfMax = n-1;
for (int index = n-1; index <= i; index--) {
if (a[index].compareTo(max) > 0) {
max = a[index];
}
}
T temp = a[i];
a[i] = a[indexOfMax];
a[indexOfMax] = temp;
}
}
}
public class Interval {
int lower = 0, upper = 0;
public Interval(int a, int b){
lower = a;
upper = b;
}
public int getLower(){
return lower;
}
public int getUpper(){
return upper;
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.