Using Binary Search to add to an ArrayList in order

Question

Hello everyone hoping you can help me here,

My problem is that I need to be able to search through an ArrayList using binary search and find where the correct place to add an object so that the list stays in order. I cannot use the collections sort as this is a homework. I have correctly implemented a boolean method that tells if the list contains an item you want to search for. That code is here:

    public static boolean search(ArrayList a, int start, int end, int val){
    int middle = (start + end)/2;
    if(start == end){
        if(a.get(middle) == val){
            return true;
        }
        else{
            return false;
        }
    }
    else if(val < a.get(middle)){
        return search(a, start, middle - 1, val);
    }
    else{
        return search(a, middle + 1, end, val); 
    }
}

What I need to do is use this method to see if the number already exists in the list and if that returns false then I need to be able to use another binary search to figure out where in the list the number (val) should go. Any help is greatly appreciated, thank you!!!

Justin

You should read up on Binary Search. You have some flaws in your implementation. — Hunter McMillen, Mar 17 '13 at 23:42

score 3 · Accepted Answer · answered Mar 17 '13 at 23:46

Well instead of returning true or false, you can return the last index in your search. So if the value isn't in the List, then return the last index you visited, and see if the value is less than or larger than the current value at that index, and add the new value accordingly.

score 2 · Answer 2 · answered Mar 18 '13 at 00:14

Instead of returning boolean value, you should return position of value, which you already found. Recurrent solution is OK, but for really big List it will be a problem to find the result. Instead of using recurrention try to implement loop-based solution. I have created a little demo, which will help you to understand it:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class SourceCodeProgram {

    private List<Integer> integers = new ArrayList<Integer>();

    public static void main(String argv[]) throws Exception {
        SourceCodeProgram test = new SourceCodeProgram();
        test.addIntegerToSortedListVerbose(10);
        test.addIntegerToSortedListVerbose(2);
        test.addIntegerToSortedListVerbose(11);
        test.addIntegerToSortedListVerbose(-1);
        test.addIntegerToSortedListVerbose(7);
        test.addIntegerToSortedListVerbose(9);
        test.addIntegerToSortedListVerbose(2);
        test.addIntegerToSortedListVerbose(5);
        test.addIntegerToSortedListVerbose(1);
        test.addIntegerToSortedListVerbose(0);
    }

    private void addIntegerToSortedListVerbose(Integer value) {
        int searchResult = binarySearch(integers, value);
        System.out.println("Value: " + value + ". Position = " + searchResult);
        integers.add(searchResult, value);

        System.out.println(Arrays.toString(integers.toArray()));
    }

    private int binarySearch(List<Integer> list, Integer value) {
        int low = 0;
        int high = list.size() - 1;

        while (low <= high) {
            int mid = (low + high) / 2;
            Integer midVal = list.get(mid);
            int cmp = midVal.compareTo(value);

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

Program prints:

Value: 10. Position = 0
[10]
Value: 2. Position = 0
[2, 10]
Value: 11. Position = 2
[2, 10, 11]
Value: -1. Position = 0
[-1, 2, 10, 11]
Value: 7. Position = 2
[-1, 2, 7, 10, 11]
Value: 9. Position = 3
[-1, 2, 7, 9, 10, 11]
Value: 2. Position = 1
[-1, 2, 2, 7, 9, 10, 11]
Value: 5. Position = 3
[-1, 2, 2, 5, 7, 9, 10, 11]
Value: 1. Position = 1
[-1, 1, 2, 2, 5, 7, 9, 10, 11]
Value: 0. Position = 1
[-1, 0, 1, 2, 2, 5, 7, 9, 10, 11]

Thanks for the tip, my solution must be a recursive one to satisfy the project though unfortunately. — justin henricks, Mar 18 '13 at 02:45

Using Binary Search to add to an ArrayList in order

2 Answers2

Linked