[ 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 >= lo)
{
mid = (lo + hi) / 2;
if(arr[mid] == key) return mid;
if ( key < arr[mid] ) hi = mid-1;
else lo = mid+1;
}
return _____;
}
Answer 1
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).
Answer 2
See Arrays.binarySearch.
return -low - 1;
A negative number, at most -1. As mid (the insertion point) ranges from 0.
returns
index of the search key, if it is contained in the array; otherwise, (-(insertion point) - 1). The insertion point is defined as the point at which the key would be inserted into the array: the index of the first element greater than the key, or a.length if all elements in the array are less than the specified key. Note that this guarantees that the return value will be >= 0 if and only if the key is found.
