Java - Recursive Binary Search through Arraylist

Question

So I need help with a method. using a recursive binary search algorithm to search through an arraylist.

    private static < E extends Employee > int binarySearch(ArrayList<E> list, int firstElem, int lastElem, String searchLastName)
{       
    int middle=0;

    if(firstElem > lastElem){
        return -1;
    }

    middle = (firstElem + lastElem) / 2;

    if(list.get(middle).getLastName().equals(searchLastName)){
        return middle;
    }else if(             ){ // <-------------?
        return binarySearch(list,middle+1,lastElem, searchLastName);
    }
    else {
        return binarySearch(list, firstElem, middle -1, searchLastName);            
    }
}

This is what I have so far but I'm stuck on the logic part. Any help would be appreciated.

Answer 1

Since you say you're stuck on the logic part, I think a pseudo-code answer suffices.

First of all, I'm assuming your array is sorted in ascending order. If the array is not sorted, binary search is not possible. Because it is sorted, you can keep cutting the problem size in half with each comparison. So if the answer is in the right part of the array, you throw out the left part and only recurse into the right part.

Because with every recursive call the problem gets half as small, you get a running time of O(log n).

The basic logic is like this:

binarySearch(list,begin,end,query)
    if (begin > end)
        return -1
    middle = (begin + end) / 2
    if list[middle].value == query
        return middle
    if list[middle].value < query
        return binarySearch(list,begin,middle,query)
    return binarySearch(list,middle,end,query)

Answer 2

Here you are

You have to implement a compare method to decide which half you'll search in.

I did a simple method to compare two strings .. it converts is to the a number value.

Check this sample code:

import java.util.ArrayList;

public class BinarySearch {

    public static void main(String[] args) {
        ArrayList<Employee> arrayList = new ArrayList<Employee>();
        for (int i = 0; i < 10; i++) {
            Employee employee = new Employee();
            employee.setLastName("name" + i);
            arrayList.add(employee);
        }
        System.out.println(arrayList);
        System.out
                .println(binarySearch(arrayList, 0, arrayList.size(), "name6"));

    }

    private static <E extends Employee> int binarySearch(ArrayList<E> list,
            int firstElem, int lastElem, String searchLastName) {
        int middle = 0;

        if (firstElem > lastElem) {
            return -1;
        }

        middle = (firstElem + lastElem) / 2;

        if (list.get(middle).getLastName().equals(searchLastName)) {
            return middle;
        } else if (compare(searchLastName, list.get(middle).getLastName()) >= 0) { // <-------------?
            return binarySearch(list, middle + 1, lastElem, searchLastName);
        } else {
            return binarySearch(list, firstElem, middle, searchLastName);
        }
    }

    /**
     * Compare to strings.
     * @param str1
     * @param str2
     * @return
     */
    public static int compare(String str1, String str2) {
        int minLength = Math.min(str1.length(), str2.length());
        if (getValue(str1, minLength) > getValue(str2, minLength)) {
            return 1;
        } else {
            return -1;
        }
    }

    /**
     * Calculate a value to a string to compare it.
     * @param str
     * @param length
     * @return
     */
    public static int getValue(String str, int length) {

        int result = 0;

        for (int i = 0; i < length; i++) {
            char c = str.charAt(i);
            result += Math.pow(10, i) * c;
        }

        return result;
    }

}

Here's a sample output:

[name0, name1, name2, name3, name4, name5, name6, name7, name8, name9]
6

I hope this could help.