Java

public boolean BinarySearch(int first, int last, int item) {

int mid = (first+last)/2;

if (first > last) return false;

if (item == a[mid]) return true;

if (item

if (item > a[mid]) return BinarySearch(mid+1, last, item);

return false;

}

public boolean BinarySearch(int first, int last, int item) int mid - (first+last) /2; if (first> last) return false; if (itema [mid]) return true; if (item a [mid]) return BinarySearch (mid+1, last, item) return false; Let's discuss it - it's a recursive function and it returns a boolean value And, then let's incorporate it in our ListArrayMain program to test it. Homework: 1. Set up an array of 100000000 (one hundred million!!) from 1 to 100000000 and search for an integer that is NOT in the array and time it to find out how long it takes to find it. Compare the binarv search time with the linear search time. Do this several times to see if binary search is really faster. ON PAPER, report on the running times that compare Binary and Linear search. You may have to look up how to time the execution of a Java program You may lose points if your report is illegible or grammatically incorrect or incomplete. 2. Write ON PAPER another binary search method - say, BinarySearch2, which returns the actual cell number where the item is found- or returns -1 if it's not found