Rather than implementing your own binary search, you can just use Arrays.binarySearch(int[] a, int key), then adjust the returned value accordingly.
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.
Your rules didn't specify which index to return when there are multiple valid choices (#3 or #4 with multiple equal values, or #5 with equidistant values), so the code below has code making an explicit choice. You can remove the extra code, if you don't care about ambiguities, or change the logic if you disagree with my decision to resolve it.
Note that when return value is <0, returnValue = -insertionPoint - 1, which means that insertionPoint = -returnValue - 1, which in code below mean -idx - 1. Index prior to insertion point is therefore -idx - 2.
The methods may of course return out-of-range index values (-1 or arr.length), so caller always need to check for that. For closest() method, that can only happen if array is empty, in which case it returns -1.
public static int smaller(int[] arr, int target) {
int idx = Arrays.binarySearch(arr, target);
if (idx < 0) {
// target not found, so return index prior to insertion point
return -idx - 2;
}
// target found, so skip to before target value(s)
do {
idx--;
} while (idx >= 0 && arr[idx] == target);
return idx;
}
public static int smallerOrEqual(int[] arr, int target) {
int idx = Arrays.binarySearch(arr, target);
if (idx < 0) {
// target not found, so return index prior to insertion point
return -idx - 2;
}
// target found, so skip to last of target value(s)
while (idx < arr.length - 1 && arr[idx + 1] == target) {
idx++;
}
return idx;
}
public static int biggerOrEqual(int[] arr, int target) {
int idx = Arrays.binarySearch(arr, target);
if (idx < 0) {
// target not found, so return index of insertion point
return -idx - 1;
}
// target found, so skip to first of target value(s)
while (idx > 0 && arr[idx - 1] == target) {
idx--;
}
return idx;
}
public static int bigger(int[] arr, int target) {
int idx = Arrays.binarySearch(arr, target);
if (idx < 0) {
// target not found, so return index of insertion point
return -idx - 1;
}
// target found, so skip to after target value(s)
do {
idx++;
} while (idx < arr.length && arr[idx] == target);
return idx;
}
public static int closest(int[] arr, int target) {
int idx = Arrays.binarySearch(arr, target);
if (idx >= 0) {
// target found, so skip to first of target value(s)
while (idx > 0 && arr[idx - 1] == target) {
idx--;
}
return idx;
}
// target not found, so compare adjacent values
idx = -idx - 1; // insertion point
if (idx == arr.length) // insert after last value
return arr.length - 1; // last value is closest
if (idx == 0) // insert before first value
return 0; // first value is closest
if (target - arr[idx - 1] > arr[idx] - target)
return idx; // higher value is closer
return idx - 1; // lower value is closer, or equal distance
}
Test
public static void main(String... args) {
int[] arr = {1, 4, 3, 1, 4, 6};
Arrays.sort(arr);
System.out.println(Arrays.toString(arr));
System.out.println(" | Index | Value |");
System.out.println(" | < <= ~ >= > | < <= ~ >= > |");
System.out.println("--+----------------------+---------------------+");
for (int i = 0; i <= 7; i++)
test(arr, i);
}
public static void test(int[] arr, int target) {
int smaller = smaller (arr, target);
int smallerOrEqual = smallerOrEqual(arr, target);
int closest = closest (arr, target);
int biggerOrEqual = biggerOrEqual (arr, target);
int bigger = bigger (arr, target);
System.out.printf("%d | %3d %3d %3d %3d %3d |%3s %3s %3s %3s %3s | %d%n", target,
smaller, smallerOrEqual, closest, biggerOrEqual, bigger,
(smaller < 0 ? "" : String.valueOf(arr[smaller])),
(smallerOrEqual < 0 ? "" : String.valueOf(arr[smallerOrEqual])),
(closest < 0 ? "" : String.valueOf(arr[closest])),
(biggerOrEqual == arr.length ? "" : String.valueOf(arr[biggerOrEqual])),
(bigger == arr.length ? "" : String.valueOf(arr[bigger])),
target);
}
Output
[1, 1, 3, 4, 4, 6]
| Index | Value |
| < <= ~ >= > | < <= ~ >= > |
--+----------------------+---------------------+
0 | -1 -1 0 0 0 | 1 1 1 | 0
1 | -1 1 0 0 2 | 1 1 1 3 | 1
2 | 1 1 1 2 2 | 1 1 1 3 3 | 2
3 | 1 2 2 2 3 | 1 3 3 3 4 | 3
4 | 2 4 3 3 5 | 3 4 4 4 6 | 4
5 | 4 4 4 5 5 | 4 4 4 6 6 | 5
6 | 4 5 5 5 6 | 4 6 6 6 | 6
7 | 5 5 5 6 6 | 6 6 6 | 7
Arrays.sort(arr), why not useArrays.binarySearch(arr, target)?