Sency binaria simple -- java campo con binary-search camp codereview Relacionados El problema

Simple binary seach


15
vote

problema

Español

¿Qué piensa en esta simple implementación de B Buscar en Java?

  Person6  
Original en ingles

What do you think about this simple implementation of B search in Java?

public static boolean find(int[] arrayToScan, int valueToFind) {     int startIndex = 0, endIndex = arrayToScan.length, midleIndex;     while (true) {         midleIndex = (startIndex + endIndex) / 2;         if (arrayToScan[midleIndex] == valueToFind) {             return true;         }         if (startIndex >= endIndex || midleIndex == 0 || midleIndex == arrayToScan.length - 1) {             return false;         }         if (valueToFind > arrayToScan[midleIndex]) {             startIndex = midleIndex+1 ;         }         if (valueToFind < arrayToScan[midleIndex]) {             endIndex = midleIndex-1;         }      } } 
     
         
         

Lista de respuestas

12
 
vote
vote
La mejor respuesta
 

Es una implementación limpia.

Me gusta el rendimiento potencial. No usas llamadas recursivas, por lo que esto ahorra algunas llamadas.

No me gusta (esto es una preferencia personal) Bucles infinitos con devoluciones.

Cuidado con que solo funcione en matrices ordenadas, y no hay javadoc que explique esto. Esto podría llevar a un uso incorrecto de su método.

y siempre debe cubrir los casos del borde.

Si ingresa una matriz vacía, terminará con:

    Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 0   
 

It is a neat implementation.

I like the potential performance. You don't use recursive calls, so this saves some calls.

I don't like (this is a personal preference) endless loops with returns.

Beware that it only works on sorted arrays, and there is no JavaDoc explaining this. This might lead to incorrect use of your method.

And you should always cover the edge cases.

If you input an empty array, you will end up with:

  Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 0 
 
 
         
         
10
 
vote

Hay dos inusualidades sobre este método:

  • está devolviendo un booleano (que transmite solo información mínima)
  • Usted está usando bucles infinitos en lugar de un bucle de terminación.

La primera parte puede remediarse fácilmente. En lugar de devolver un booleano, debe devolver el índice donde encontró el elemento. Tenga en cuenta que Arrays.binarySearch (la función estándar) lo hace exactamente de esa manera. Devolverá un valor negativo en caso de que el elemento no se pueda encontrar en la matriz dada.

El bucle infinito que tiene que puede fijarse de dos maneras diferentes. Ya sea mediante la recursión (que puede ser peligrosa) o utilizando un bucle debidamente limitado. La condición más sencilla que puedo pensar para el bucle para continuar es: while (startIndex != endIndex) {

Otras mejoras incluyen lo siguiente:

  • declarar variables en una línea separada para facilitar la legibilidad (e inicialización)

  • Corregir el error tipográfico en midleIndex (debe ser middleIndex )

  • AVISO QUE middleIndex Solo se necesita dentro del bucle, por lo que también podría declararlo dentro. El JIT debe ser lo suficientemente inteligente como para no reasignar esto cada vez

  • En lugar de encadenar si las declaraciones de la encadenamiento, debe considerar usar else , especialmente en las declaraciones exclusivas por pares.

    En el momento en que alcanza if (valueToFind > arrayToScan[middleIndex]) Ya sabe que el valor en middleIndex no es el que ha estado buscando. Y si no es más grande, automáticamente es más pequeño. En consecuencia, el if (valueToFind < arrayToScan[middleIndex]) no le proporciona ningún beneficio informativo . En su lugar, puede utilizar Arrays.binarySearch0 .

 

There is two unusualities about this method:

  • You're returning a boolean (which conveys only minimal information)
  • You're using infinite-loops instead of a terminating loop.

The first part can be easily remedied. Instead of returning a boolean, you should return the index where you found the element. Note that Arrays.binarySearch (the standard function) does it exactly that way. It will return a negative value in case the element could not be found in the given array.

The infinite loop you have there can be fixed in two different ways. Either by using recursion (which can be dangerous) or by using a properly limited loop. The simplest condition I can think of for the loop to continue is: while (startIndex != endIndex) {

Other improvements include the following:

  • Declare variables on a separate line to ease readability (and initialization)

  • correct the typo in midleIndex (should be middleIndex)

  • Notice that middleIndex only is needed inside the loop, so you might as well declare it inside. The JIT should be smart enough to not reallocate this every time

  • Instead of chaining if-statements, you should consider using else, especially in pairwise exclusive statements.

    The moment you reach if (valueToFind > arrayToScan[middleIndex]) you already know that the value at middleIndex is not the one you've been looking for. And if it isn't larger it automatically is smaller. Accordingly the if (valueToFind < arrayToScan[middleIndex]) doesn't provide you with any informational benefit. Instead you can just use else.

 
 
         
         
7
 
vote

Tienes algunos errores en su código, son difíciles de detectar. En muchos casos, no verá este error, pero se rompe al concepto de su "índice final". Configura su índice final para ser la longitud de la matriz, pero luego, luego, cuando el extremo se establece en el medio, se calcula como 9988777665544330 en lugar de simplemente estar configurado en middleIndex . Corregí que fuera de 1 en mi copia de su código, pero todavía tenía algunos problemas que decidí que no intentaría depurar.

Este es un error "fuera de 1", y es difícil de detectar. Ver: https://en.wikipedia.org/wiki/off-by-one_error < / a>

Además, hay una posibilidad muy remota de que se usará su código con matrices de entrada grandes (como, en las entradas muy grandes, más de 2 ^ 30 elementos ...) en cuyo caso su calculación para el punto medio puede fallar : (startIndex + endIndex) / 2; Debido a startIndex + endIndex podría desbordarse para convertirse en un número negativo, lo cual no es lo que desea. La mejor solución es usar startIndex + (endIndex - startIndex) / 2 que nunca se desbordará: https://research.googleblog.com/2006/06/extra-extra-read-all-about-it-nearly.html

Ahora, su método se llama find que espero devolver una ubicación, no un booleano. Entiendo que solo necesita hacer un cheque para ver si el valor está presente, por lo que cambiaría el nombre del método en exists .

Finalmente, no tengo ningún problema con los bucles infinitos como lo ha hecho, pero me pregunto si reducir esto a un for-loop no es mejor de todos modos ...

Escribí algún código para probar esto, y se le ocurrió:

  public static boolean exists(int[] arrayToScan, int valueToFind) {     for (int startIndex = 0, endIndex = arrayToScan.length, middleIndex = endIndex / 2;             startIndex < endIndex;             middleIndex = startIndex + (endIndex - startIndex) / 2) {         if (arrayToScan[middleIndex] == valueToFind) {             return true;         }         if (valueToFind > arrayToScan[middleIndex]) {             startIndex = middleIndex + 1;         } else {             endIndex = middleIndex;         }     }     return false; }   

Tenga en cuenta que utilizo los términos separados por comas en el inicio de For-Loop. Esto no es algo común que hacer, y tiene sus propias preocupaciones, pero estructura el bucle adecuadamente.

He reunido un caso de prueba que martina su método y mi método, y muestra cómo aparece su primer error. Consulte el código que se ejecuta en IdeOne: https://ideone.com/wegocv y busque valores "falsos" de El método find (por ejemplo, buscando 0 en la matriz middleIndex0 ....; -))

Editar: Reestructured como un ritmo-bucle de nuevo, pero con la misma configuración / condicional:

  middleIndex1  
 

You have some bugs in your code, they are hard to spot. In many cases, you won't see this bug, but it breaks down to the concept of your "end-index". You set up your end-index to be the length of the array, but then later, when end-index is set to the middle, it is calculated as middleIndex - 1 instead of just being set to middleIndex. I corrected that off-by-1 in my copy of your code, but it still had some issues that I decided I would not try to debug.

This is an "off-by-1" error, and it's hard to spot. See: https://en.wikipedia.org/wiki/Off-by-one_error

In addition, there's a very remote chance that your code will be used with large input arrays (like, very large inputs, more than 2^30 elements...) in which case your calcualtion for the mid-point may fail: (startIndex + endIndex) / 2; because startIndex + endIndex could overflow to become a negative number, which is not what you want. The better solution is to use startIndex + (endIndex - startIndex) / 2 which will never overflow: https://research.googleblog.com/2006/06/extra-extra-read-all-about-it-nearly.html

Now, your method is called find which I expect to return a location, not a boolean. I understand that you only need to do a check to see if the value is present, so I would rename the method to exists.

Finally, I don't have a problem with infinite loops like you have, but I wonder whether reducing this to a for-loop isn't better anyway....

I wrote some code to test this, and came up with:

public static boolean exists(int[] arrayToScan, int valueToFind) {     for (int startIndex = 0, endIndex = arrayToScan.length, middleIndex = endIndex / 2;             startIndex < endIndex;             middleIndex = startIndex + (endIndex - startIndex) / 2) {         if (arrayToScan[middleIndex] == valueToFind) {             return true;         }         if (valueToFind > arrayToScan[middleIndex]) {             startIndex = middleIndex + 1;         } else {             endIndex = middleIndex;         }     }     return false; } 

Note that I use comma-separated terms in the for-loop init. This is not a common thing to do, and has it's own concerns, but it structures the loop appropriately.

I have put together a test case that hammers your method, and my method, and it shows how your first bug appears. See the code running on ideone: https://ideone.com/wEgoCv and look for "false" values from the find method (e.g. searching for 0 in the array [0, 1].... ;-))

Edit: Restructured as a while-loop again, but with the same setup/conditionals:

public static boolean exists(int[] arrayToScan, int valueToFind) {     int startIndex = 0;     int endIndex = arrayToScan.length;     while (startIndex < endIndex) {         int middleIndex = startIndex + (endIndex - startIndex) / 2;         if (arrayToScan[middleIndex] == valueToFind) {             return true;         }         if (valueToFind > arrayToScan[middleIndex]) {             startIndex = middleIndex + 1;         } else {             endIndex = middleIndex;         }     }     return false; } 
 
 
       
       
1
 
vote

Sugeriría otra corrección menor, que es más una cuestión de semántica. Dado que su middleIndex2 es el índice que apunta al elemento Último de su matriz, debe ser 99887776655443313 desde middleIndex4 Devuelve el tamaño de la matriz y no la posición del último elemento.

 

I would suggest another minor correction, which is more a matter of semantics. Since your endIndex is the index that points to the last element of your array, it should be endIndex = arrayToScan.length - 1 since length returns the size of the array and not the position of the last element.

 
 
 
 
1
 
vote

usted hace dos suposiciones:

  1. La matriz está ordenada.

  2. El valor de búsqueda es, de hecho, dentro del valor establecido.

Una suposición de mi parte: si el valor está fuera del valor establecido, devuelve el valor inferior o superior según corresponda.

  middleIndex5  

que recorta cualquier búsqueda fuera de la matriz sin bucle

Mantenerse fuera de la otra "opinión" que se expresa.

 

You make two assumptions:

  1. The array is sorted.

  2. The value being searched for is in fact within the value set.

An assumption on my part: If the value is outside the value set, then return either the lower or the upper value as appropriate.

If parmvalue <= array.lowervalue then    return array.lowervalue else    if parmvalue => array.maxvalue then       return array.maxvalue    enif endif 

That trims any search outside the array with no looping

Staying out of the other "opinion" being expressed.

 
 
1
 
vote

Me gusta a veces usar una notación matemática más sistemática para estos algoritmos tales, ya que realmente ayuda a hacer que la sintaxis sea más explicativa automática.

Por lo tanto, si en cambio, se planteó el problema original en una notación más sucinta como:

  public static boolean find(int[] ary, int val) {     int i = 0, n = ary.length, m;     while( true ) {         m = (i + n) / 2;         if( ary[m] == val ) {             return true;         }         if( i >= n || m == 0 || m == ary.length - 1 ) {             return false;         }         if( val > ary[m] ) {             i = m + 1;         }         if( val < ary[m] ) {             n = m - 1;         }                } }   

Luego, cuando se refactora, es mucho más fácil comparar y evaluar las principales diferencias de los algoritmos de un vistazo. TOMAR, por ejemplo, esta respuesta desde arriba:

  public static boolean exists(int[] ary, int val) {     for (int i = 0, n = ary.length, m = n / 2;             i < n;             m = i + (n - i) / 2) {         if (ary[m] == val) {             return true;         }         if (val > ary[m]) {             i = m + 1;         } else {             n = m;         }     }     return false; }   

Tenga en cuenta que utilizo los términos separados por comas en el inicio de For-Loop. Esto no es algo común que hacer, y tiene sus propias preocupaciones, pero estructura el bucle adecuadamente.

He reunido un caso de prueba que martina su método y mi método, y muestra cómo aparece su primer error. Consulte el código que se ejecuta en IdeOne: https://ideone.com/wegocv y busque valores "falsos" de el método de búsqueda (por ejemplo, buscando 0 en la matriz [0, 1] ....; -))

Editar: Reestructured como un ritmo-bucle de nuevo, pero con la misma configuración / condicional:

  public static boolean exists(int[] ary, int val) {     int i = 0;     int n = ary.length;     int m = n / 2;     while (i < n) {         if (ary[m] == val) {             return true;         }         if (val > ary[m]) {             i = m + 1;         } else {             n = m;         }         m = i + (n - i) / 2     }     return false; }   
 

I like to sometimes use a more systematic mathematical notation for these such algorithms as it really helps to make the syntax more self explanatory.

So, if instead the original problem was posed in a more succinct notation like:

public static boolean find(int[] ary, int val) {     int i = 0, n = ary.length, m;     while( true ) {         m = (i + n) / 2;         if( ary[m] == val ) {             return true;         }         if( i >= n || m == 0 || m == ary.length - 1 ) {             return false;         }         if( val > ary[m] ) {             i = m + 1;         }         if( val < ary[m] ) {             n = m - 1;         }                } } 

Then when refactoring, it is much easier to compare and evaluate the main differences of the algorithms at a glance. Take for example this answer from above:

public static boolean exists(int[] ary, int val) {     for (int i = 0, n = ary.length, m = n / 2;             i < n;             m = i + (n - i) / 2) {         if (ary[m] == val) {             return true;         }         if (val > ary[m]) {             i = m + 1;         } else {             n = m;         }     }     return false; } 

Note that I use comma-separated terms in the for-loop init. This is not a common thing to do, and has it's own concerns, but it structures the loop appropriately.

I have put together a test case that hammers your method, and my method, and it shows how your first bug appears. See the code running on ideone: https://ideone.com/wEgoCv and look for "false" values from the find method (e.g. searching for 0 in the array [0, 1].... ;-))

Edit: Restructured as a while-loop again, but with the same setup/conditionals:

public static boolean exists(int[] ary, int val) {     int i = 0;     int n = ary.length;     int m = n / 2;     while (i < n) {         if (ary[m] == val) {             return true;         }         if (val > ary[m]) {             i = m + 1;         } else {             n = m;         }         m = i + (n - i) / 2     }     return false; } 
 
 
 
 
0
 
vote
  endIndex = arrayToScan.length - 1  if (startIndex >= endIndex || midleIndex == 0 || midleIndex == arrayToScan.length - 1) {     return false; }   

llegará allí con

  if (startIndex >= endIndex) {     return false; }    

solo puede poner lo anterior en un tiempo

puede tratar con = de otra manera

¿Por qué no devolver el índice real?
Puede devolver el índice para el mismo costo
Simplemente está usando mucho más código de lo que necesita

  public static int indexOf(int[] a, int key) {     int lo = 0;     int hi = a.length - 1;     while (lo <= hi) {         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; }   

 
endIndex = arrayToScan.length - 1  if (startIndex >= endIndex || midleIndex == 0 || midleIndex == arrayToScan.length - 1) {     return false; } 

you will get there with

if (startIndex >= endIndex) {     return false; }  

can just put the above in a while

can deal with = in an else

Why not return the actual index?
You can return the index for the same cost
You just are using a lot more code than you need to

public static int indexOf(int[] a, int key) {     int lo = 0;     int hi = a.length - 1;     while (lo <= hi) {         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; } 
 
 
   
   
0
 
vote

La reescritura de la API existente es siempre peligrosa. Mejor uso existente Arrays.binarySearch . Sugeriría la implementación más simple y confiable:

  public static boolean find(int[] arrayToScan, int valueToFind) {     return Arrays.binarySearch(arrayToScan, valueToFind) > -1; }   
 

Rewriting of existing API is always dangerous. Better use existing Arrays.binarySearch. I would suggest the simplest and most reliable implementation:

public static boolean find(int[] arrayToScan, int valueToFind) {     return Arrays.binarySearch(arrayToScan, valueToFind) > -1; } 
 
 

Relacionados problema

5  BinarySearch Kata en Ruby  ( Binarysearch kata in ruby ) 
Acabo de completar esta búsqueda binaria Kata, que tiene algunos requisitos extraños, y pasé un poco "limpiando" mi código y haciéndolo más compacto. Agradece...

2  Encontrar el subconjunto máximo de intervalos no superpuestos  ( Finding the max subset of non overlapping intervals ) 
¿Cómo podría este código ser más limpio? Creo que la forma en que manejo las interfaces y la búsqueda binaria podría mejorarse. Estoy tratando de entender cóm...

7  Búsqueda binaria de Java (y obtenga índice si no está allí) Revisión  ( Java binary search and get index if not there review ) 
Quiero hacer una búsqueda binaria y si el objetivo no está allí, obtenga el índice de donde debería haber sido. Este es el código en el que se me ocurrió. P...

2  Búsqueda binaria, usando  ( Binary search using remove ) 
Soy consciente de que existe una función en la biblioteca estándar. Por favor, dame comentarios sobre buenos convenciones y estándares de codificación. fun...

3  ¿Es esta búsqueda binaria cerca de Idiomatic OCAML?  ( Is this binary search close to idiomatic ocaml ) 
let binsearch ~arr ~cmp x = ( let cmpx = cmp x in (* Assuming arr is ordered according to cmp, then (bs min max) is an *) (* index of a value v...

5  Búsqueda binaria: primera / última / ocurrencia aleatoria  ( Binary search first last random occurrence ) 
He escrito un código para "búsqueda binaria" una lista, y devolver el primera ocurrencia del objetivo: def bsearch(a, left, right, target, first_or_last ...

5  Búsqueda binaria eficiente  ( Efficient binary search ) 
Mi implementación: 157 Implementación normal: 158 La diferencia de ser mi implementación hace una conjetura en el índice del valor en función de l...

2  Eliminación de un nodo en un árbol de búsqueda binario  ( Deletion of a node in a binary search tree ) 
Estoy buscando ver si mi implementación del método de eliminación / eliminación en un árbol de búsqueda binario es suficiente, legible y se ejecuta en un tiem...

10  Encuentre el duplicado en una matriz ordenada en menos de O (n)  ( Find the duplicate in a sorted array in less than on ) 
suposiciones: La matriz está ordenada. solo hay un duplicado. La matriz solo se rellena con números [0, N], donde n es la longitud de la matriz. Eje...

1  Retroalimentación de búsqueda binaria  ( Binary search feedback ) 
He escrito un algoritmo de búsqueda binario, pero parece ser un poco diferente a otras personas que he visto. Esperaba que la comunidad pudiera darme algunos ...




© 2022 respuesta.top Reservados todos los derechos. Centro de preguntas y respuestas reservados todos los derechos