JAVA - Binary search - return index of key

Question

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:

If the search key is in the array - it returns the smallest index i for which a[i] is equal to the key
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
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!

b.t.w - is this a homework assignment? (If so, please tag it accordingly) — RonK
– RonK, Commented Apr 25, 2011 at 20:05

Nick · Accepted Answer · 2020-08-05 00:05:08Z

1

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.

edited Aug 5, 2020 at 0:05

Nick

147k23 gold badges67 silver badges106 bronze badges

answered Apr 25, 2011 at 19:56

RonK

9,6728 gold badges54 silver badges90 bronze badges

Sign up to request clarification or add additional context in comments.

6 Comments

ISJ Over a year ago

@RonK Hi, yep, I tried that one, but I wasn't sure what the Int equivalent of compareTo is... Is it possible you can show me in the right direction? Thanks!

ColinD Over a year ago

@ISJ: The equivalent of compareTo for ints is... normal <, >=, etc.

RonK Over a year ago

@ISJ - If you use int instead of String it should make the basic assumption of your API to be correct (that the Array is sorted and that comparison works correctly).

RonK Over a year ago

@ISJ - I think that the end of the main should be: int index = search(key, a); System.out.println("Index = " + index); System.out.println("Value = " + a[index]); Something like that (if I fully understood the requirement)

RonK Over a year ago

@ISJ: One last comment - i missed the question about compareTo for int. Replace the line int cmp = a[mid].compareTo(key); with int cmp = a[mid] - key; it will do the trick.

|

Paŭlo Ebermann · Accepted Answer · 2011-04-25 19:52:51Z

1

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?

answered Apr 25, 2011 at 19:52

Paŭlo Ebermann

75k20 gold badges150 silver badges217 bronze badges

2 Comments

ISJ Over a year ago

@Ebermann Ok, so if it is not there it should test for greater than or smaller than and then return the respective index??

Paŭlo Ebermann Over a year ago

Your conditions for the result are a bit strange, but I think one of return -hi, return -hi-1` and return -hi + 1 does what you want. (Make some tests on paper, and get clear what you really want here.) There might be a special case for hi == a.length.

Collectives™ on Stack Overflow

JAVA - Binary search - return index of key

2 Answers 2

6 Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

6 Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related