Exercise 1:

In computer science, binary search, also known as half-interval search, is an efficient search algorithm that finds the position of a target value within a sorted array, by comparing the target value to the middle element, and then repeating the process by splitting that half of the subarray again, and so on until the target is found. BinarySearch is much faster than linear search, for large arrays. A linear search is a search that starts from the top and searches all items or until the item is found, like looking for a name in a phonebook by starting from the beginning until the name is found.

Both simple arrays and ArrayLists have built-in implementations of binary search, but to use binarySearch, the list must be sorted.

Efficient searching is a major topic of Data Structures and Algorithms so this assignment will give you a basic understanding of some of the fundamentals of efficient searching and more practice with arrays and ArrayLists.

For this project, you will create two classes representing two data structure components for searching and managing lists of integers. The two classes from the user's point of view share identical interfaces and operations but have very different underlying data structures, one using a simple array of integers, the other an ArrayList of type Integer.

The two classes you will create will implement the operations defined in the interface as shown in the UML class diagram above.

In addition, BinarySearchArray will implement a static method testBinarySearchArray() that populates the lists, and lets the user interactively test the two classes by adding and removing elements. The parameter BinarySearch can represent either class and tells testBinarySearchArray which class to test.

Steps to Implement:

1) To get started create a new project in IntelliJ called BinarySearch. Add a class to your project called BinarySearchArray. Then add another class BinarySearchArrayList and an interface called BinarySearch. The interface BinarySearch includes public method stubs as shown in the diagram. You are allowed to add BinarySearchArrayList to the same file as BinarySearch but don't add an access modifier to this class, or for easier reading, you can declare the classes in separate files with public access modifiers. Only the class containing the main method can be defined as public in files defining multiple classes.

You should read up on interfaces if you are unfamiliar. An interface provides a template for defined behavior to a class that inherits from the interface. The implementation is left to the implementing class. A class that implements an interface must implement ALL the methods declared in the interface, unless the class inherits from another class that already implements one or more of those methods.

This is convenient because different classes that implement the same interface solve a similar problem but in a different way. The interface is a promise of certain general behavior, and the concrete class provides the concrete specialized implementation. A GrazingMammal nurses (an abstraction or interface). A Cow nurses(a concrete object).

2) The two classes you will define are as follows:

public class BinarySearchArray implements BinarySearch { } class BinarySearchArrayList implements BinarySearch{ }

Since you are implementing the interface, as mentioned you must provide implementations of the interface methods exactly as defined in the interface. The interface has only the declarations. These methods will have the same signature as the interface but may be implemented very differently, as is the case in this assignment. This is logical since one class operates on arrays, the other on ArrayLists.

Implementation Details (See the BinarySearch interface above - method name correspond to interface and class definitions)

Method Name	Arrays - How to implement	Comments	ArrayList	Comments
sort	Arrays.sort()	import java.util.Arrays	Collections.sort	import java.util.Collections
binarySearch	Arrays.binarySearch()	Arrays.binarySearch(arr,key). Returns a negative number if not present, otherwise return index.	Collections.binarySearch()	Collections.binarySearch(arrList, key)
remove(index)	No api method available	Requires shifting up items below item being remove.	remove(index)	arrList.remove(index);
boolean contains(value)	Use binarySearch or a for loop to determine if key is present in the array. No api method.	binarySearch return a negative number if not present, otherwise returns index.	boolean contains(value)	arrList.contains(Integer.valueOf(value))
add(int value)	No api method available	An "empty" element is marked by a zero value. If no zeros, print an error message "no space available"	add(int value)	arrList.add(value);
initializeArray()			initializeArray()	Same as array class.
printElements()	No api method available	Prints the elements of the array on a single line delimited by spaces and newline at end of line. Uses arr.	printElements()	Prints the elements of the array on a single line delimited by spaces and newline at end of line. Uses arrList.
public static void testBinarySearchArray(BinarySearch searchObject) This method is part of BinarySearchArray class. Use bsArr for parameter	See the discussion below on how to implement.	Test driver method to be called from main. Takes parameter of BinarySearch which indicates the method which class to test.	Same as array version	Use static method BinarySearchArray. testBinarySearchArray(bsArrList)
intializeArray, add, remove		For both array and ArrayList, call sort and printElements after each of these methods.		For both array and arrayList, call sort and printElements after each of these methods.
main() from class BinarySearchArray	BinarySearchArray bsArr = new BinarySearchArray(); bsArr.initializeArray(); bsArr.sort();BinarySearchArray-1.java bsArr.printElements(); BinarySearchArray.testBinarySearchArray(bsArr);			BinarySearchArrayList bsArrList = new BinarySearchArrayList(); bsArrList.initializeArray(); bsArrList.sort(); bsArrList.printElements(); BinarySearchArray.testBinarySearchArray(bsArrList);

Interactive Test Driver testBinarySearchArray() Code and pseudocode:

Use a do-while loop to interactively test the array or ArrayList. Array has a capacity limit that requires error checking while ArrayList does not .

Download a stubbed-out version of the program if you wish, that includes the completed test driver but will require you to write code for key methods.

//// Code and pseudocode -- main driver of your

public static void testBinarySearchArray(BinarySearch searchObject) { System.out.println(" Welcome to the Binary Search Test. "); int value = 0; try { System.out.print("Enter an integer to search (or -1 or  D to quit): "); String ss = scanner.nextLine(); value = Integer.parseInt(ss); // TODO: Implement this pseudoscode --do { // Use binarySearch to try to find index of value, e.g. -- index= bsArr.binarySearch(value) // use bsArr or bsArrayList objects method calls. Index gives index of element or // negative number // if found -- if (index > 0)) { -- Print(Value x is found. Do you want to delete? y/n -- scan for y/n --if (y) { -- remove(index); --Call sort // using bsArray or bsArrayList object --Call printElements() ///using bsArray or bsArrayList } } -- else { -- print (Value x not found. Do you want to add it (y/n); -- Scan for y/n } -- if (y) { -- Check for capacity, error if no capacity (array only) -- else { -- Call bsArr.add() or bsArrayList.add() -- Call sort and printElements as before. } } } -- Print("Enter an integer to search (or  D to quit): "); -- scan and parseInt } while (!ss.equals("-1")); } catch (NoSuchElementException e) { System.out.println("Goodbye..."); } }

Sample output:

// array object case, the zeros are empty slots 0 0 0 0 0 3 4 14 15 17 19 20 21 23 25 Welcome to the Array List Test. Enter an integer to search (or -1 or  D to quit): 18 Value 18 not found. Do you want to add it? y/n? y 0 0 0 0 3 4 14 15 17 18 19 20 21 23 25 Enter an integer to search (or  D to quit): 22 Value 22 not found. Do you want to add it? y/n? y 0 0 0 3 4 14 15 17 18 19 20 21 22 23 25 Enter an integer to search (or  D to quit): 22 Value 22 found. Do you want to remove it? y/n? y 0 0 0 0 3 4 14 15 17 18 19 20 21 23 25 Enter an integer to search (or  D to quit): 19 Value 19 found. Do you want to remove it? y/n? y 0 0 0 0 0 3 4 14 15 17 18 20 21 23 25 Enter an integer to search (or  D to quit): -1

// ArrayList Object 3 4 5 6 14 17 18 19 20 25

Welcome to the Array List Test.

Enter an integer to search (or -1 or  D to quit): 21 Value 21 not found. Do you want to add it? y/n? y 3 4 5 6 14 17 18 19 20 21 25 Enter an integer to search (or  D to quit): 22 Value 22 not found. Do you want to add it? y/n? y 3 4 5 6 14 17 18 19 20 21 22 25 Enter an integer to search (or  D to quit): 23 Value 23 not found. Do you want to add it? y/n? n Enter an integer to search (or  D to quit): 23 Value 23 not found. Do you want to add it? y/n? y 3 4 5 6 14 17 18 19 20 21 22 23 25 Enter an integer to search (or  D to quit): ^D Goodbye...