Java BinarySearch

Question

¿Puedo obtener ayuda, por favor? He intentado muchos métodos para que esto funcione. Obtuve la matriz ordenada e imprimida, pero después de eso mi función de búsqueda binaria no quiere funcionar y me da los resultados correctos. Siempre me da -1. ¿Alguna ayuda?

public class BinarySearch { 
public static final int NOT_FOUND = -1; 
public static int binarySearch(double[] a, double key) { 
    int low = 0; 
    int high = a.length -1; 
    int mid; 
    while (low<=high) { 
     mid = (low+high) /2; 
     if (mid > key) 
      high = mid -1; 
     else if (mid < key) 
      low = mid +1; 
     else 
      return mid; 
    } 
    return NOT_FOUND; 
} 
public static void main(String[] args) { 
    double key = 10.5, index; 
    double a[] ={10,5,4,10.5,30.5}; 
    int i; 
    int l = a.length; 
    int j; 
    System.out.println("The array currently looks like"); 
    for (i=0; i<a.length; i++) 
     System.out.println(a[i]); 
    System.out.println("The array after sorting looks like"); 
    for (j=1; j < l; j++) { 
     for (i=0; i < l-j; i++) { 
      if (a[i] > a[i+1]) { 
       double temp = a[i]; 
       a[i] = a[i+1]; 
       a[i+1] = temp; 
      } 
     } 
    } 
    for (i=0;i < l;i++) { 
     System.out.println(a[i]); 
    } 
    System.out.println("Found " + key + " at " + binarySearch(double a[], key)); 
} 
} 

Answer 1

usted no está realmente comparando con los valores de la matriz. en

while (low <= high) { 
     mid = (low + high)/2; 
     if (mid > key) { 
      high = mid - 1; 
     } else if (mid < key) { 
      low = mid + 1; 
     } else { 
      return mid; 
     } 
} 

En lugar de utilizar esta sección

while (low <= high) { 
     mid = (low + high)/2; 
     if (a[mid] > key) { 
      high = mid - 1; 
     } else if (a[mid] < key) { 
      low = mid + 1; 
     } else { 
      return mid; 
     } 
    } 

Tenías razón para encontrar los índices, pero lo que estaba haciendo es que se acaba de comparando el número de índice con su clave, que es obviamente incorrecto. Cuando escriba a[mid], en realidad comparará su clave con el número que está en el índice mid.

también la última línea de código está dando error de compilación, debe ser

System.out.println("Found " + key + " at " + binarySearch(a, key)); 

Answer 2

Aquí

if (mid > key) 
     high = mid -1; 
    else if (mid < key) 
     low = mid +1; 
    else 
     return mid; 

Usted está comparando el índice a un valor (key) en matriz. En su lugar debe compara con a[mid]

Y,

System.out.println("Found " + key + " at " + binarySearch(double a[], key)); 

Debe ser

System.out.println("Found " + key + " at " + binarySearch(a, key)); 

Answer 3

public static double binarySearch(double[] a, double key) { 

    if (a.length == 0) { 
     return -1; 
    } 
    int low = 0; 
    int high = a.length-1; 

    while(low <= high) { 
     int middle = (low+high) /2; 
     if (b> a[middle]){ 
     low = middle +1; 
     } else if (b< a[middle]){ 
     high = middle -1; 
     } else { // The element has been found 
     return a[middle]; 
     } 
    } 
    return -1; 
    } 

Answer 4

alguna manera encuentro la versión iterativa no es fácil de leer, la repetición hace que sea agradable y fácil :-)

public class BinarySearch { 

    private static int binarySearchMain(int key, int[] arr, int start, int end) { 
     int middle = (end-start+1)/2 + start; //get index of the middle element of a particular array portion 

     if (arr[middle] == key) { 
      return middle; 
     } 

     if (key < arr[middle] && middle > 0) { 
      return binarySearchMain(key, arr, start, middle-1); //recurse lower half 
     } 

     if (key > arr[middle] && middle < arr.length-1) { 
      return binarySearchMain(key, arr, middle+1, end); //recurse higher half 
     } 

     return Integer.MAX_VALUE; 
    } 

    public static int binarySearch(int key, int[] arr) { //entry point here 
     return binarySearchMain(key, arr, 0, arr.length-1); 
    } 

} 

Answer 5

Aquí hay una solución sin muchos. Lo mismo se puede hacer en una matriz. Si necesitamos encontrar 'k' números más grandes, tomamos una matriz de tamaño 'k' poblada con los primeros k elementos de la fuente de datos principal. Ahora, siga leyendo un elemento y colóquelo en la matriz de resultados, si tiene un lugar.

public static void largestkNumbers() { 
    int k = 4; // find 4 largest numbers 
    int[] arr = {4,90,7,10,-5,34,98,1,2}; 
    int[] result = new int[k]; 

    //initial formation of elems 
    for (int i = 0; i < k; ++i) { 
     result[i] = arr[i]; 
    } 
    Arrays.sort(result); 

    for (int i = k; i < arr.length; ++i) { 
     int index = binarySearch(result, arr[i]); 
     if (index > 0) { 
     // insert arr[i] at result[index] and remove result[0] 
     insertInBetweenArray(result, index, arr[i]); 
     } 
    } 
    } 

    public static void insertInBetweenArray(int[] arr, int index, int num) { 
    // insert num at arr[index] and remove arr[0] 
    for (int i = 0 ; i < index; ++i) { 
     arr[i] = arr[i+1]; 
    } 
    arr[index-1] = num; 
    } 

    public static int binarySearch(int[] arr, int num) { 

    int lo = 0; 
    int hi = arr.length - 1; 
    int mid = -1; 

    while(lo <= hi) { 
     mid = (lo+hi)/2; 
     if (arr[mid] > num) { 
     hi = mid-1; 
     } else if (arr[mid] < num) { 
     lo = mid+1; 
     } else { 
     return mid; 
     } 
    } 
    return mid; 
    } 

Answer 6

int BinSearch(int[] array, int size, int value) 
{ 
    if(size == 0) return -1; 
    if(array[size-1] == value) return size-1; 
    if(array[0] == value) return 0; 
    if(size % 2 == 0) { 
     if(array[size-1] == value) return size-1; 
     BinSearch(array,size-1,value); 
    } 
    else 
    { 
     if(array[size/2] == value) return (size/2); 
     else if(array[size/2] > value) return BinSearch(array, (size/2)+1, value); 
    else if(array[size/2] < value) return (size/2)+BinSearch(array+size/2, size/2, value); 
    } 
} 

o

Binary Search in Array

Answer 7

/** 
    * Find whether 67 is a prime no 
    * Domain consists 25 of prime numbers 
    * Binary Search 
    */ 

    int primes[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97}; 

    int min = 0, 
      mid, 
      max = primes.length, 
      key = 67, 
      count= 0; 

    boolean isFound = false; 


    while (!isFound) { 
     if (count < 6) { 
      mid = (min + max)/2; 
      if (primes[mid] == key) { 
       isFound = true; 
       System.out.println("Found prime at: " + mid); 
      } else if (primes[mid] < key) { 
       min = mid + 1; 
       isFound = false; 
      } else if (primes[mid] > key) { 
       max = mid - 1; 
       isFound = false; 
      } 
      count++; 

     } else { 
      System.out.println("No such number"); 
      isFound = true; 
     } 

    } 

Answer 8

/** 
HOPE YOU LIKE IT 
A.K.A Binary Search 
Take number array of 10 elements, input a number a check whether the number 
is present: 
**/ 
package array; 
import java.io.InputStreamReader; 
import java.io.BufferedReader; 
import java.io.IOException; 
class BinaryS 
{ 
    public static void main(String args[]) throws IOException 
    {  
    BufferedReader br=new BufferedReader(new InputStreamReader(System.in));  
    System.out.print("Enter a number: "); 
    int n=Integer.parseInt(br.readLine()); 
    int a[]={10,20,30,40,50,60,70,80,90,100}; 
    int upper=a.length-1,lower=0,mid; 
    boolean found=false; 
    int pos=0; 
    while(lower<=upper) 
    { 
     mid=(upper+lower)/2; 
     if(n<a[mid])upper=mid-1; 
     else if(n>a[mid])lower=mid+1; 
     else 
     { 
      found=true; 
      pos=mid; 
      break; 
     } 
    } 
    if(found)System.out.println(n+" found at index "+pos); 
    else System.out.println(n+" not found in array"); 
} 
}