Búsqueda binaria en matriz

Question

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

Answer 1

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

Cualquier estructura de datos indexada/de acceso aleatorio puede buscarse 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). Estos son algunos ejemplos de Wikipedia: Binary Search Algorithm:

recursiva:

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

La versión de comparación solo 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; 
} 

Answer 3

depende de si usted tiene la repetición de un elemento en su matriz o no y si le importan o no los resultados múltiples. 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 el https://github.com/m-vahidalizadeh/foundations/blob/master/src/algorithms/BinarySearchExample.java. Espero que ayude.