# How do I return an index of where a number should go if it isn't found in a Binary Search in JAVA - Java

TAGS :
Viewed: 2 - Published at: a few seconds ago

#### [ How do I return an index of where a number should go if it isn't found in a Binary Search in JAVA ]

So I have a binary search code that finds where a number should be placed to maintain sorted order. I've been at this for a little over an hour and a half so far trying to figure this out so I could use a push along.

What value would I return at the end of the method if the value is not found in the array, but the place it should be placed is found? Basically a value that says the index where this number belongs is within +/- 1 of the mid value.

Here is the binary search, i'm not looking to change it but rather just looking for the variable to return where the _____ is.

``````private static int bsearch( int[] arr, int count, int key )
{
if (count==0) return -1;
int lo = 0, hi = count - 1, mid;
while(hi &gt;= lo)
{
mid = (lo + hi) / 2;
if(arr[mid] == key) return mid;
if ( key &lt; arr[mid] ) hi = mid-1;
else lo = mid+1;
}
return _____;
}
``````

Most methods return the bitwise negation of the index where to place the element, thus `~idx`.

Binary search makes the assumption that all elements before `lo` are less than the `key` and analogue for `hi`.

In case `hi < lo`, it means that `hi` was set to `mid-1` and `mid` was equal to `lo` (because `hi` and `lo` differ at most one) or analogue to `lo`. Thus the location where the element must be placed is at `lo`. One thus returns:

``````return ~lo;
``````

An optimized version of the algorithm is thus:

``````private static int bsearch( int[] arr, int count, int key) {
if (count==0) return -1;
int lo = 0, hi = count - 1, mid = hi>>1;
while(hi >= lo) {
mid = (lo + hi) >> 1;
if ( key < arr[mid] ) hi = mid-1;
else if ( key > arr[mid] ) lo = mid+1;
else return mid;
}
return ~lo;
}
``````

As a testcase:

``````for(int i = 0; i <= 22; i++) {
int r = bsearch(new int[] {2,3,7,9,11,15,21},7,i);
System.out.println(""+i+" -> "+r+" "+(~r));
}
``````

gives:

``````0 -> -1 0
1 -> -1 0
2 -> 0 -1
3 -> 1 -2
4 -> -3 2
5 -> -3 2
6 -> -3 2
7 -> 2 -3
8 -> -4 3
9 -> 3 -4
10 -> -5 4
11 -> 4 -5
12 -> -6 5
13 -> -6 5
14 -> -6 5
15 -> 5 -6
16 -> -7 6
17 -> -7 6
18 -> -7 6
19 -> -7 6
20 -> -7 6
21 -> 6 -7
22 -> -8 7
``````

`x -> i j` with `i` the result and `j` the bitwise negative (used as insertion index in case `i` is negative).

``````return -low - 1;
A negative number, at most -1. As `mid` (the insertion point) ranges from 0.