Implementing binary search on an array of Strings

Question

I'm having a bit of trouble with this. The input array is based on file input and the size of the array is specified by the first line in the file. The binarySearch method seems to look alright but it doesn't seem to be working would. Anybody be able to help? Thanks.

public static int binarySearch(String[] a, String x) {
    int low = 0;
    int high = a.length - 1;
    int mid;

    while (low <= high) {
        mid = (low + high) / 2;

        if (a[mid].compareTo(x) < 0) {
            low = mid + 1;
        } else if (a[mid].compareTo(x) > 0) {
            high = mid - 1;
        } else {
            return mid;
        }
    }

    return -1;
}

public static void main(String[] args) {

    Scanner input = new Scanner(System.in);

    System.out.println("Enter the name of your file (including file extension): ");
    String filename = input.next();

    String[] numArray;
    try (Scanner in = new Scanner(new File(filename))) {
        int count = in.nextInt();

        numArray = new String[count];

        for (int i = 0; in.hasNextInt() && count != -1 && i < count; i++) {
            numArray[i] = in.nextLine();
        }

        for (int i = 0; i < count; i++) //printing all the elements
        {
            System.out.println(numArray[i]);
        }

        String searchItem = "The";

        System.out.println("The position of the String is:");
        binarySearch(numArray, searchItem);

    } catch (final FileNotFoundException e) {
        System.out.println("That file was not found. Program terminating...");
        e.printStackTrace();

    }

}

Selfwill

Is the array in sorted order when you call binarySearch? – Reremouse

Yea their sorted. When the elements in the array are printed their all coming out as null for some reason. – Selfwill

In what way is this not working? What is the expected behavior vs the actual behavior? What have you tried? – Globetrotter

Just curious, is this a homework assignment? Arrays.sort(numArray); Arrays.binarySearch(numArray, "The"); could replace most of this code. – Lagunas

Answer 1

I have added following example for your further referance.

import java.util.Arrays;

public class BinaryStringSearch {

    public static void main(String[] args) {

        String array[] ={"EWRSFSFSFSB","BB","AA","SDFSFJ","WRTG","FF","ERF","FED","TGH"};
        String search = "BB";

        Arrays.sort(array);

        int searchIndex = binarySearch(array,search);

        System.out.println(searchIndex != -1 ? array[searchIndex]+ " - Index is "+searchIndex : "Not found");
    }

    public static int binarySearch(String[] a, String x) {
        int low = 0;
        int high = a.length - 1;
        int mid;

        while (low <= high) {
            mid = (low + high) / 2;

            if (a[mid].compareTo(x) < 0) {
                low = mid + 1;
            } else if (a[mid].compareTo(x) > 0) {
                high = mid - 1;
            } else {
                return mid;
            }
        }

        return -1;
    }

}

Berny

Answer 2

I hope it will help:

 public static void main(String ar[]){

    String str[] = {"account","angel","apple","application","black"};
    String search= "application";
    int length = str.length-1;
    BinarySearchInString findStrin = new BinarySearchInString();
    int i = findStrin.find(str, 0, length, search);
    System.out.println(i);
}

  public int find(String first[], int start, int end, String searchString){
    int mid = start + (end-start)/2;

    if(first[mid].compareTo(searchString)==0){
        return mid;
    }
    if(first[mid].compareTo(searchString)> 0){
        return find(first, start, mid-1, searchString);
    }else if(first[mid].compareTo(searchString)< 0){
        return find(first, mid+1, end, searchString);
    }
    return -1;
  }

Blister

Please include explanation of how your code fixes the bug rather than just lots of code – Daphne

Answer 3

As spotted by @Mike Rylander you forgot to output the result.

You should use Arrays.binarySearch instead of your own implementation.

(As a general rule, JRE libraries are well-tested, well-documented and fast. I googled "java binary search" and this question is well-ranked. I had a try with @Thusitha Indunil's code, which didn't appear to work. I googled harder and found Arrays.binarySearch, which worked.)

Strafford

Answer 4

I believe that your problem is that you forgot to output the results. Try replacing binarySearch(numArray, searchItem); with System.out.println(binarySearch(numArray, searchItem));

Globetrotter

Answer 5

There are four issues that I can spot in addition to the already mentioned missing print of the result.

1: You have a String[] called numArray and you are searching for a String, "The" the name numArray is possibly a bit mis-leading.

2: I assume you have some sort of specified input file format where the number of String in the file are specified by an integer as the first token in the file. This is ok however, as a condition in the for loop that populates the numArray there is in.hasNextInt(), and the next token is taken out of the Scanner using in.nextLine(). You should use complementing check/removal methods such as in.hasNext() with in.next(). Check out the Scanner API.

3: The binarySearch(String[], String) method uses String.compareTo(String). This is determines a lexicographical ordering of this String to the parameter String. Trying to compare upper case to lower case may not yield what you expect, as "the".compareTo("The") will not result in 0. You should check out the String API for options to either force all of your input to one case, maybe while reading the file, or use a different flavor of a compare to method.

4: The last thing that I see may be considered a bit of a corner case, however with a sufficiently large String array, and a search string that may reside far in the right side, ie. high index side, of the array you may get an ArrayIndexOutOfBoundsException. This is because (low + high) can result in a negative value, when the result "should" be greater than Integer.MAX_VALUE. Then the result is divided by two and still yields a negative value. This can be solved by bit shifting the result instead of dividing by 2, (low + high) >>> 1. Joshua Bloch has a great article about this common flaw in divide and conquer algorithms.

Bankston

Answer 6

    int low = fromIndex;
    int high = toIndex - 1;

    while (low <= high) {
        int mid = (low + high) >>> 1;

        Comparable midVal = (Comparable) a[mid];

        int cmp = midVal.compareTo(key);

        if (cmp < 0)
            low = mid + 1;
        else if (cmp > 0)
            high = mid - 1;
        else
            return mid;
    }
    return -(low + 1);
}

Faviolafavonian

I would suggest to explain your answer, not simply paste code. – Sandasandakan