algorithm - pseint - busqueda binaria recursiva

Búsqueda binaria en matriz

Question

¿Cómo implementaría una búsqueda binaria usando solo una matriz?

Answer 1

Asegúrese de que su matriz esté ordenada, ya que este es el quid de una búsqueda binaria.

Cualquier estructura de datos indexada / de acceso aleatorio puede ser buscada binariamente. Entonces, cuando dice usar "solo una matriz", yo diría que las matrices son la estructura de datos más básica / común en la que se emplea una búsqueda binaria.

Puede hacerlo recursivamente (más fácil) o iterativamente. La complejidad temporal de una búsqueda binaria es O (log N), que es considerablemente más rápida que una búsqueda lineal para verificar cada elemento en O (N). Aquí hay algunos ejemplos de Wikipedia: Algoritmo de búsqueda binaria :

Recursivo:

BinarySearch(A[0..N-1], value, low, high) {
if (high < low)
return -1 // not found
mid = low + ((high - low) / 2)
if (A[mid] > value)
return BinarySearch(A, value, low, mid-1)
else if (A[mid] < value)
return BinarySearch(A, value, mid+1, high)
else
return mid // found
}

Iterativo:

 BinarySearch(A[0..N-1], value) {
low = 0
high = N - 1
while (low <= high) {
mid = low + ((high - low) / 2)
if (A[mid] > value)
high = mid - 1
else if (A[mid] < value)
low = mid + 1
else
return mid // found
}
return -1 // not found
}

Answer 2

Depende si tiene repetición de un elemento en su matriz o no y si le interesan los resultados múltiples o no. Tengo dos métodos en esta implementación. Uno de ellos devuelve solo el primer hallazgo, pero el otro devuelve todos los hallazgos de la clave.

import java.util.Arrays;
public class BinarySearchExample {
//Find one occurrence
public static int indexOf(int[] a, int key) {
int lo = 0;
int hi = a.length - 1;
while (lo <= hi) {
// Key is in a[lo..hi] or not present.
int mid = lo + (hi - lo) / 2;
if (key < a[mid]) hi = mid - 1;
else if (key > a[mid]) lo = mid + 1;
else return mid;
}
return -1;
}
//Find all occurrence
public static void PrintIndicesForValue(int[] numbers, int target) {
if (numbers == null)
return;
int low = 0, high = numbers.length - 1;
// get the start index of target number
int startIndex = -1;
while (low <= high) {
int mid = (high - low) / 2 + low;
if (numbers[mid] > target) {
high = mid - 1;
} else if (numbers[mid] == target) {
startIndex = mid;
high = mid - 1;
} else
low = mid + 1;
}
// get the end index of target number
int endIndex = -1;
low = 0;
high = numbers.length - 1;
while (low <= high) {
int mid = (high - low) / 2 + low;
if (numbers[mid] > target) {
high = mid - 1;
} else if (numbers[mid] == target) {
endIndex = mid;
low = mid + 1;
} else
low = mid + 1;
}
if (startIndex != -1 && endIndex != -1){
System.out.print("All: ");
for(int i=0; i+startIndex<=endIndex;i++){
if(i>0)
System.out.print('','');
System.out.print(i+startIndex);
}
}
}
public static void main(String[] args) {
// read the integers from a file
int[] arr = {23,34,12,24,266,1,3,66,78,93,22,24,25,27};
Boolean[] arrFlag = new Boolean[arr.length];
Arrays.fill(arrFlag,false);
// sort the array
Arrays.sort(arr);
//Search
System.out.print("Array: ");
for(int i=0; i<arr.length; i++)
if(i != arr.length-1){
System.out.print(arr[i]+",");
}else{
System.out.print(arr[i]);
}
System.out.println("/nOnly one: "+indexOf(arr,24));
PrintIndicesForValue(arr,24);
}
}

Para obtener más información, visite https://github.com/m-vahidalizadeh/foundations/blob/master/src/algorithms/BinarySearchExample.java . Espero que ayude.

Answer 3

La única versión de comparación es rápida y concisa

int bsearch_double(const double a[], int n, double v) {
int low = 0, mid;
while (n - low > 1) {
mid = low + (n - low) / 2;
if (v < a[mid]) n = mid;
else low = mid;
}
return (low < n && a[low] == v) ? low : -1;
}