CODEWITHSUNDEEP
javarecursionbinary-search
ISJ
ISJ

Reputation: 509

JAVA - Binary search - return index of key

I have the following problem I need to solve, but is strugling a bit. Would really appreciate it if someone can help.

In short in comes down to the following:

  1. If the search key is in the array - it returns the smallest index i for which a[i] is equal to the key
  2. If the search key is not in the array but greater - it returns the smallest index i as -i where a[i] is greater than the key
  3. If the search key is not in the array but smaller - it returns -j where j is the index of the last element in the array

I have the code of searching for the key, but I'm not sure how to return the indexes as mentioned above...

import java.util.Arrays; 
public class BinarySearchIndex2 {

    // a working recursive version
    public static int search(String key, String[] a) {
        return search(key, a, 0, a.length);
    }

    public static int search(String key, String[] a, int lo, int hi) {
        // possible key indices in [lo, hi)
        if (hi <= lo) return -1;

        int mid = lo + (hi - lo) / 2;
        int cmp = a[mid].compareTo(key);
        if      (cmp > 0) return search(key, a, lo, mid);
        else if (cmp < 0) return search(key, a, mid+1, hi);
        else              return mid;
    }

    public static void main(String[] args) {

        String key = args[0];
        int sizeoflist = StdIn.readInt();
        String[] a = new String[sizeoflist];
            int counter = 0; //counter for while loop to fill array a

        while (!StdIn.isEmpty()){

            a[counter] = StdIn.readString();
            counter++;

        }

        Arrays.sort(a); // sort the words (if needed)

        if ( search(key, a) < 0) ; /* System.out.println();*/
        else if ( search(key, a) > 0 ) ;
        else if ( search(key, a) = 0 ) ;

    }
}

Would be really glad if someone can help me with this matter...

Thanks!

Upvotes: 0

Views: 3291

Answers (2)

RonK
RonK

Reputation: 9652

String.compareTo performs a lexicographical comparison. This means that it can decide that "50">"100", whereas clearly 50<100 is what you would expect. This will affect your Arrays.sort call so your Array is already messed up.

Is it a must to have public static int search(String key, String[] a) as your API?

If you can change it to be public static int search(int key, int[] a) it will make your API work (assuming you don't have any bugs I missed).

Hope this was what you were referring to.

Edit: some fine tuning to the problem analysis.

Upvotes: 1

Paŭlo Ebermann
Paŭlo Ebermann

Reputation: 74790

The important point is here:

    if (hi <= lo) return -1;

This occurs when you got an sub-array to search of size zero, which means that the element is not there. Now think: what does the specification say about the return value here?

Upvotes: 1

Related Questions