Description
(a) Write the following Java method (your code should probably be under twenty lines):
public static int firstNonSmallerIndex(int[] array, int value)
The method takes in an array in sorted order and a value, and returns the smallest possible
index of an element that is equal to or larger than the given value (or -1 if the value is larger
than the max).
Your method must run in O(log N) time provided the list has few duplicates.
Assuming array = {1,2,3,3,3,4,5,5,14,17}, here are some example calls:
Method call Return value
firstNonSmallerIndex(array, 3) 2
firstNonSmallerIndex(array, 4) 5
firstNonSmallerIndex(array, -1) 0
firstNonSmallerIndex(array, 23) -1
firstNonSmallerIndex(array, 15) 9
Hint: Your code will look similar to binary search. Once you have found one non-smaller
index, it doesn’t mean that it is the first non-smaller index. In other words, you should keep
on searching until you are sure you have found the first non-smaller index.
(b) After implementing your method in Java and ensuring that it is correct, run timing tests
on your method with arrays of different sizes. Use the method
createRandomSortedArray (shown later) and System.nanoTime() (see
http://docs.oracle.com/javase/6/docs/api/java/lang/System.html#nanoTime%28%29) to help
you create random sorted arrays and run your timing tests. Answer the following questions:
• What array sizes did you choose and why?
• What were the runtimes of each array size?
• Did your runtimes increase as you expected according to the Big-Oh of your algorithm?
Why or why not?
For part (a), your firstNonSmallerIndex method should be found in a class named
FirstNonSmaller and should be saved in a file named FirstNonSmaller.java.
Turn in FirstNonSmaller.java electronically by submitting it to the turn-in link on the
homework webpage.
For part (b), you can save the code/methods you use to do your timing tests in
FirstNonSmaller.java–we will not grade your timing code. However, we will grade
your answers to the questions above. Save your answers in a file named README.txt and
also submit that file using the same turn-in link on the homework webpage.
import java.util.*;
….
public static int[] createRandomSortedArray(int size) {
Random rand = new Random();
int[] array = new int[size];
for (int i = 0; i < size; i++) {
// pick random numbers (subtract a bit so that some
// are negative)
array[i] = rand.nextInt(size * 3) – size / 4;
}
Arrays.sort(array);
return array;
}