Búsqueda binaria en matriz

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

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 } 

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 

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

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; } 

Implementé el código siguiente en Java, simple y rápido / ** * Búsqueda binaria utilizando Recursion * @author asharda * * / public class BinSearch {

  /** * Simplistic BInary Search using Recursion * @param arr * @param low * @param high * @param num * @return int */ public int binSearch(int []arr,int low,int high,int num) { int mid=low+high/2; if(num >arr[high] || num arr[mid]) { return binSearch(arr,low+1,high, num); } }//end of while return -1; } public static void main(String args[]) { int arr[]= {2,4,6,8,10}; BinSearch s=new BinSearch(); int n=s.binSearch(arr, 0, arr.length-1, 10); String result= n>1?"Number found at "+n:"Number not found"; System.out.println(result); } } 

Búsqueda binaria en Javascript (ES6)

(Si alguien necesita)

De abajo hacia arriba:

 function binarySearch (arr, val) { let start = 0; let end = arr.length - 1; let mid; while (start <= end) { mid = Math.floor((start + end) / 2); if (arr[mid] === val) { return mid; } if (val < arr[mid]) { end = mid - 1; } else { start = mid + 1; } } return -1; } 

Recursividad :

 function binarySearch(arr, val, start = 0, end = arr.length - 1) { const mid = Math.floor((start + end) / 2); if (val === arr[mid]) { return mid; } if (start >= end) { return -1; } return val < arr[mid] ? binarySearch(arr, val, start, mid - 1) : binarySearch(arr, val, mid + 1, end); }