Dada la array de enteros ordenados, la clave de búsqueda y las preferencias de búsqueda encuentran la posición de la array. Las preferencias de búsqueda pueden ser:
1) IGUAL: busca solo la clave igual o -1 si no se encuentra. Es una búsqueda binaria normal.
2) EQUAL_OR_SMALLER: busca solo la clave igual o la más pequeña más cercana. -1 si no se encuentra.
3) EQUAL_OR_BIGGER: busque solo la clave igual o la más grande más cercana. -1 si no se encuentra.
Ejemplos:
Input : { 0, 2, 4, 6 }, key -1, EQUAL
Output : -1
Input : { 0, 2, 4, 6 }, key -1, EQUAL_OR_BIGGER
Output : 0
Input : { 0, 2, 4, 6 }, key 7, EQUAL_OR_BIGGER
Output : -1
Input : { 0, 2, 4, 6 }, key 7, EQUAL_OR_SMALLER
Output : 3
En el algoritmo de búsqueda binaria regular, la evaluación y la división se realizan en la medida en que el tamaño del subarreglo sea mayor que 0.
En nuestro caso, si queremos mantener una función única, debemos realizar la evaluación final en un subarreglo de tamaño = 2. Solo en tamaño de subarreglo == 2 es posible verificar las condiciones EQUAL_OR_SMALLER y EQUAL_OR_BIGGER.
En el siguiente código, SC significa Criterios de búsqueda .
public class BinarySearchEqualOrClose {
private static void printResult(int key, int pos,
SC sC)
{
System.out.println("" + key + ", " + sC + ":" + pos);
}
enum SC {
EQUAL,
EQUAL_OR_BIGGER,
EQUAL_OR_SMALLER
};
public static int searchEqualOrClose(int key, int[] arr, SC sC)
{
if (arr == null || arr.length == 0) {
return -1;
}
if (arr.length == 1) { // just eliminate case of length==1
// since algorithm needs min array size==2
// to start final evaluations
if (arr[0] == key) {
return 0;
}
if (arr[0] < key && sC == SC.EQUAL_OR_SMALLER) {
return 0;
}
if (arr[0] > key && sC == SC.EQUAL_OR_BIGGER) {
return 0;
}
return -1;
}
return searchEqualOrClose(arr, key, 0, arr.length - 1, sC);
}
private static int searchEqualOrClose(int[] arr, int key,
int start, int end, SC sC)
{
int midPos = (start + end) / 2;
int midVal = arr[midPos];
if (midVal == key) {
return midPos; // equal is top priority
}
if (start >= end - 1) {
if (arr[end] == key) {
return end;
}
if (sC == SC.EQUAL_OR_SMALLER) {
// find biggest of smaller element
if (arr[start] > key && start != 0) {
// even before if "start" is not a first
return start - 1;
}
if (arr[end] < key) {
return end;
}
if (arr[start] < key) {
return start;
}
return -1;
}
if (sC == SC.EQUAL_OR_BIGGER) {
// find smallest of bigger element
if (arr[end] < key && end != arr.length - 1) {
// even after if "end" is not a last
return end + 1;
}
if (arr[start] > key) {
return start;
}
if (arr[end] > key) {
return end;
}
return -1;
}
return -1;
}
if (midVal > key) {
return searchEqualOrClose(arr, key, start, midPos - 1, sC);
}
return searchEqualOrClose(arr, key, midPos + 1, end, sC);
}
public static void main(String[] args)
{
int[] arr = new int[] { 0, 2, 4, 6 };
// test full range of xs and SearchCriteria
for (int x = -1; x <= 7; x++) {
int pos = searchEqualOrClose(x, arr, SC.EQUAL);
printResult(x, pos, SC.EQUAL);
pos = searchEqualOrClose(x, arr, SC.EQUAL_OR_SMALLER);
printResult(x, pos, SC.EQUAL_OR_SMALLER);
pos = searchEqualOrClose(x, arr, SC.EQUAL_OR_BIGGER);
printResult(x, pos, SC.EQUAL_OR_BIGGER);
}
}
}
-1, EQUAL:-1 -1, EQUAL_OR_SMALLER:-1 -1, EQUAL_OR_BIGGER:0 0, EQUAL:0 0, EQUAL_OR_SMALLER:0 0, EQUAL_OR_BIGGER:0 1, EQUAL:-1 1, EQUAL_OR_SMALLER:0 1, EQUAL_OR_BIGGER:1 2, EQUAL:1 2, EQUAL_OR_SMALLER:1 2, EQUAL_OR_BIGGER:1 3, EQUAL:-1 3, EQUAL_OR_SMALLER:1 3, EQUAL_OR_BIGGER:2 4, EQUAL:2 4, EQUAL_OR_SMALLER:2 4, EQUAL_OR_BIGGER:2 5, EQUAL:-1 5, EQUAL_OR_SMALLER:2 5, EQUAL_OR_BIGGER:3 6, EQUAL:3 6, EQUAL_OR_SMALLER:3 6, EQUAL_OR_BIGGER:3 7, EQUAL:-1 7, EQUAL_OR_SMALLER:3 7, EQUAL_OR_BIGGER:-1
Complejidad de tiempo: O (log n)
Publicación traducida automáticamente
Artículo escrito por LeonidPurgalin y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA