Write the following Java Method (your code should probably be under twenty lines

Question

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 orader 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(logN) time provided the list has few duplicates.

For example, if arr = {1,2,3,3,3,4,5,5,14,17}, then firstNonsmallerIndex(arr, 3) returns 2, firstNonsmallerIndex(arr, 4) returns 5, firstNonsmallerIndex(arr, -1) returns 0, firstNonsmallerIndex(arr, 23) returns -1, and firstNonsmallerIndex(arr, 15) returns 9.

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.nonoTime()

(see http://docs.oracle.com/javase/6/docs/api/java/lang/System.html) (nano time %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++)

            {

                        array[i] = rand.nextInt(size*3) – size/4;

            }

Arrays.sort(array);

Return array;

}

Explanation / Answer

This is the code we have for you. You will find all your code inside the class.

import java.util.Arrays;

import java.util.Random;

/**
*
* @author Sam
*/
public class ArraySearch {
    public static int firstnonsmallerindex (int[] array, int value) {
        if (array[0] >= value)
            return 0;
        int left, right, mid;
        left = 1;
        right = array.length - 1;
        mid = (left + right) / 2;
        while (!(array[mid] >= value && array[mid - 1] < value) && left <= right) {
            if (value <= array[mid])
                right = mid - 1;
            else if (value > array[mid])
                left = mid + 1;
          
            mid = (left + right) / 2;
        }
        if (array[mid] >= value && array[mid - 1] < value)
            return mid;
        return -1;
    }
  
    public static int[] createrandomsortedarray (int size){

            Random rand = new Random();
            int[] array = new int[size];
            for(int i=0; i<size;i++) {
                        array[i] = rand.nextInt(size*3) - size/4;
            }
    Arrays.sort(array);
    return array;
    }
  
  
    public static void main(String[] args) {
        /* // Test cases
        int[] arr = {1,2,3,3,3,4,5,5,14,17};
      
        System.out.println(firstnonsmallerindex(arr, 3));
        System.out.println(firstnonsmallerindex(arr, 4));
        System.out.println(firstnonsmallerindex(arr, -1));
        System.out.println(firstnonsmallerindex(arr, 23));
        System.out.println(firstnonsmallerindex(arr, 15));          
        */
        Random r = new Random(System.currentTimeMillis());
        System.out.println("Size time(ns)");
        for (int i = 0; i < 10; i++) {
            int[] arr = createrandomsortedarray(r.nextInt(10000) + 10000);
            long timeStart = System.nanoTime();
            firstnonsmallerindex(arr, 15);
            long time = System.nanoTime() - timeStart;
            System.out.println(arr.length + " " + time);
        }
    }
}

Experimental output:

run:

run:
Size   time(ns)
13895   9408
18341   4277
13539   2994
18855   8125
14177   6842
19020   4276
10215   5987
16933   5559
11171   5132
19735   5987

Since the time varied to a great extent it is hard to comment. As you can see an array of size 19735    takes 5987ns, and also size 19020    takes only 4276ms. So it is better not to comment.

If you have any doubt, please put it in the commernt section. feel free to ask me if you are facing any trouble

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.