Using Binary Search to Find Insertion Points in an Array

Question

I need to modify the below code to use binary search to return the Index of an Insertion Point in a sorted Array

for Instance if objArray={1,2,4} and searchObj=3

the binarysearch function should return 2 as the Index where 3 should be inserted

public int binarySearch(Comparable[] objArray, Comparable searchObj)
{
    int low = 0;
    int high = objArray.length - 1;
    int mid = 0;
    while (low <= high)
    {
        mid = (low + high) / 2;
        if (objArray[mid].compareTo(searchObj) < 0)
        {
            low = mid + 1;
        }
        else if (objArray[mid].compareTo(searchObj) > 0)
        {
            high = mid - 1;
        }
        else
        {
            return mid;
        }
    }
    return -1;
}

Thanks

Start by indenting your code, so that you (and we) can read it. Then, ask a question. — JB Nizet, Oct 01 '17 at 21:24
"I need to modify the below code ..." How's the modification going? Did you hit a roadblock? Can you explain what input causes your method to malfunction? — Sergey Kalinichenko, Oct 01 '17 at 21:25
Think over what happens after the first iteration through your code..do you get your answer right away? — Naman, Oct 01 '17 at 21:27
To clarify, when you say "I need to modify the below code", did you really mean "I need someone to modify the below code"? (If so, you're not going to find that person here.) — Joe C, Oct 01 '17 at 21:38
See my answer here: https://stackoverflow.com/questions/39416560/how-can-i-simplify-this-working-binary-search-code-in-c/39417165#39417165 — Matt Timmermans, Oct 02 '17 at 01:32

score 0 · Accepted Answer · answered Oct 03 '17 at 05:09

Your code is a Binary Search, which returns the index of the element or -1 if it didn't exists at all.

If you just need to return the index where it should be inserted, then you should change your line return -1; to return mid;.

But keep in mind that this approach will return either the index of that element OR the index where it should be inserted. So you will need another test to identify if the item already exists in your array.

Maybe, a better approach would be to use a Binary Tree.

Using Binary Search to Find Insertion Points in an Array

1 Answers1