Generic Binary Search Using String

Question

I have a generic binary search which functions properly for Integers in an Array. However, when applied to an Array of Strings it will only return at most three of the indexes correctly ([1],[2],[3]), while marking the others as nonexistent ([-1]). Thanks in advance for any insight.

public class BinarySearch {

private BinarySearch() { }

private static <T extends Comparable<? super T>> int search(T[] list, int first, int last, T key){
    int foundPosition;
    int mid = first + (last - first) / 2;  
    if (first > last)
        foundPosition = -1;
    else if (key.equals(list[mid]))
        foundPosition = mid;
    else if (key.compareTo(list[mid]) < 0)
        foundPosition = search(list, first, mid - 1, key);
    else
        foundPosition = search(list, mid + 1, last, key);
    return foundPosition;
} 

public static void main(String args[]) {
    //Integer
    Integer [] searchInteger = {0,2,4,6,8,10,12,14,16};
    int integerLast = searchInteger.length-1;
    System.out.println("Integer test array contains...");
        for (Integer a1 : searchInteger) {
         System.out.print(a1 + " ");
        }
    System.out.println("\nChecking Integer array...");
    int result;
    for (int key = -4; key < 18; key++) {
        result = BinarySearch.search(searchInteger, 0, integerLast, key);
        if (result < 0)
            System.out.println(key + " is not in the array.");
        else
            System.out.println(key + " is at index " + result + ".");
        }
    //String
    String[] searchFruits = {"lemon", "apple", "banana", "peach", "pineapple", "grapes", "blueberry", "papaya"};      
    System.out.println("String test array contains...");
    for (String a1 : searchFruits) {
        System.out.print(a1 + " ");
    }
    System.out.println("\nChecking String array...");
    int results;
    int fruitLast = searchFruits.length-1;
    for (int key = 0; key < searchFruits.length; key++){
        results = BinarySearch.search(searchFruits, 0, fruitLast, searchFruits[key]);
        System.out.println("Key = " + searchFruits[key]);
        System.out.println("Index result = " + results);
        if (results < 0)
            System.out.println(searchFruits[key] + " is not in the array.");
        else
            System.out.println(searchFruits[key] + " is at index " + results + ".");        
    }
}
}

Karthik · Accepted Answer · 2015-07-13 19:36:05Z

2

Because your String array

    String[] searchFruits = {"lemon", "apple", "banana", "peach", "pineapple", "grapes", "blueberry", "papaya"};

is not sorted, where as your integer array

  Integer [] searchInteger = {0,2,4,6,8,10,12,14,16};

is sorted.

By the way you could have used Arrays.binarySearch() too.

edited Jul 13, 2015 at 19:36

answered Jul 13, 2015 at 19:24

Karthik

5,0387 gold badges39 silver badges67 bronze badges

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

Collectives™ on Stack Overflow

Generic Binary Search Using String

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related