Question 1: Binary Search
Using Java, implement a method to use binary search on an ArrayList of Integers. The form of
the method given in L3Q1.java is as seen below. The search algorithm must run in O( log n)
The motivation for this question is to show one reason why sorted lists are important; it
enables binary search which takes O (log n) time to find an element in a list. While we are
already discussing faster ways to do this using maps and sets, it is important to see binary
search which helps motivate tress and other ideas within data structures.
For our binary search to be properly in Mimir we ask you to find the index first occurrence of
the value in your list or return -1 if it is not in the list. This means once your binary search finds
the element, we want you to use a loop to see if the element before is a duplicate and if so
update the index you return. An example of what we mean is that for the list “1 9 9 9 9”,
searching for 9 could result in 4 of the 5 indexes. The result we expect is index 1, while binary
search would first result in index 2 we walk back through the duplicates to find the first
occurrence. We will ignore the walking back from an efficiency perspective, the walk back is so
everyone gets the same answer regardless of implementation.
Alex’s Pseudo Code for binary search on an array(list) can be found in the middle slides of his
lecture 5. His pseudo code is a single method that will find an occurrence of the value. This will
pass most of the tests on Mimir. Then you will have to add at the end of the method outside of
the main loop the duplicates case discussed above.
The submitted file should be L3Q1.java