CODEWITHSUNDEEP
javaarraysif-statementwhile-loopbinary-search
A.J.
A.J.

Reputation: 97

Using Binary Search to open up a space in an array at the correct index

I am supposed to create two methods: The first method, bSearch, is a binary search algorithm. The second method, insertInOrder, is supposed to take the index we got from the bSearch method and find that index in the array, open up a spot at that index by shifting all other elements of that array over, and insert the key/ int at that index.

The ints will be received from a text file containing 25 ints. I am not to make any copies or extra arrays to do this, and I am supposed to encode and then decode the index in the insertInOrder method. In these methods, key will be the current int read from the file of ints, and count will count the number of ints which have been received. I am basically building my own sort method, I can't call any outside methods, and the array is not to be out of order at any time.

I have filled in these methods, but I am a shaky on my understanding. I think my problem is that in the bSearch method, because I can't get it to return anything but 0. I can't get it to return the new value of mid, which is the index where the key/ int is supposed to be inserted. Than you for your help. The code is below:

    static void insertInOrder( int[] arr, int count, int key   )
    {
        int index=bSearch( arr, count, key ); 

        int encodedIndex = -(index+1);
        int decodedIndex = -(index+1);

        for (int i = index; i > 0; i--)
        {
            arr[i] = arr[i-1];
        }

        arr[index]=key; 
    }


    static int bSearch(int[] a, int count, int key)
    {
        int lo = 0;
        int hi = a.length-1;
        int index = 0;
        boolean found = false;
        while (!found && lo <= hi)
        {   
            int mid = lo + ((hi - lo) / 2);
            if (a[mid] == key)
            {
                found = true;
                index = mid;        
            }
            else if (a[mid] > key)
            {
                hi = mid -1;
            }
            else
            {
                lo = mid +1;
            }
        }   
        return index;
    }

Upvotes: 2

Views: 325

Answers (1)

Brion
Brion

Reputation: 746

Your binary search method works correctly for a pre-filled array.

The problem is during insertion into the array, the binary search returns 0 if the value doesn't exist in the array instead of providing the correct insert position.

In this case, you probably need track how many values are current used in the array. Is that what the value "count" is for? In that case, you should start your "hi" value at count instead of the max length and you need to return the count as the index if you've reached the end of the array without finding a value.

Update: You can use this binary search to return insertion position.

    int lo = 0;
    int hi = count-1;
    int index = 0;
    boolean found = false;
    while (!found && lo < hi)
    {
        int mid = lo + ((hi - lo) / 2);
        if (a[mid] == key)
        {
            found = true;
            index = mid;
        }
        else if (a[mid] > key)
        {
            hi = mid;
            index = hi;
        }
        else
        {
            lo = mid +1;
            index = lo;
        }
    }
    return index;

Upvotes: 1

Related Questions