Please write your solution based on the partial code from attached OrderedApp.java.

3.1: (Remove Duplicates from Ordered Array). Add a method called RemoveDuplicates() remove the duplicates in place such that each element appear only once and return the new length.

The description of RemoveDuplicates() is:

public int RemoveDuplicates()

In this method, return the new length of the array if duplicates are removed; or else, return 0 which means that no duplicates exist;

Add some code in main() to test this method. You should have two test cases: one returns the new length after duplicates are removed; then recall this method and returns 0.

Example:

Given input array nums = [1,1,2], Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively. It doesn't matter what you leave beyond the new length.

(After you finish your source code, please analyze the time complexity used for your algorithm. Put your analysis in answers part of your lab report.) (please answer)

3.2: (Binary search exercise). Consider the following list:

2 10 17 45 49 55 68 85 92 98 110

Using the binary search, how many comparisons are required to determine whether the following items are in the list? Show the values of lowerBound (LB), upperBound (UB), and curIn, and the number of comparisons after each iteration of the loop.

Note: there are four items (a-d) to search, dont miss any.

a) 15:

Iteration	LB	UB	CurIn	a[CurIn]	No of comparisons
1	0	10	5	55	3

This is an unsuccessful/successful search. The total number of comparisons is **. (The red font should be replaced by your answer)

b)49; c)98; d)99;

// orderedArray.java // demonstrates ordered array class // to run this program: C>java OrderedApp //////////////////////////////////////////////////////////////// class OrdArray { private long[] a; // ref to array a private int nElems; // number of data items //----------------------------------------------------------- public OrdArray(int max) // constructor { a = new long[max]; // create array nElems = 0; } //----------------------------------------------------------- public int size() { return nElems; } //----------------------------------------------------------- public int find(long searchKey) { int lowerBound = 0; int upperBound = nElems-1; int curIn; while(true) { curIn = (lowerBound + upperBound ) / 2; if(a[curIn]==searchKey) return curIn; // found it else if(lowerBound >= upperBound) return nElems; // can't find it else // divide range { if(a[curIn] < searchKey) lowerBound = curIn + 1; // it's in upper half else upperBound = curIn - 1; // it's in lower half } // end else divide range } // end while } // end find() //----------------------------------------------------------- public void insert(long value) // put element into array { int j; for(j=0; j value) // (linear search) break; for(int k=nElems; k>j; k--) // move bigger ones up a[k] = a[k-1]; a[j] = value; // insert it nElems++; // increment size } // end insert() //----------------------------------------------------------- public boolean delete(long value) { int j = find(value); if(j==nElems) // can't find it return false; else // found it { for(int k=j; k