/*
+----------------------------------------+
| BUSQUEDA BINARIA (BUSQUEDA DICOTOMICA) |
+----------------------------------------+

        En este  programa se realiza  una búsqueda binaria  (llamada
también dicotómica) en un vector ordenado de números enteros.

        Este  algoritmo  es   válido  exclusivamente  para  vectores
ordenados y consiste  en comparar en primer lugar  con la componente
central del vector,  y si no es igual al  valor buscado se reduce el
intervalo  de búsqueda  a la  mitad derecha  o izquierda según donde
pueda  encontrarse el  valor a  buscar. El  algoritmo termina  si se
encuentra el valor buscado o si  el tamaño del intervalo de búsqueda
queda anulado.

        En los casos  en que existan repeticiones en  el vector, del
valor buscado,  este algoritmo obtendrá uno  de ellos aleatoriamente
según  los  lugares  que   ocupen,  los  cuales  necesariamente  son
consecutivos.
*/

#include <stdio.h>  /* printf (), getchar () */

void main (void)
{
  int vector [100];     /* declaración de un vector de 100
                         elementos int */
  int x,                /* contiene valor a buscar */
  encontrado,           /* variable que sólo toma dos valores:
                        cierto (1) o falso (0) */
  i, centro, izquierda, derecha; /* índices de vector */

  /* Escritura de la cabecera. */
  printf ("BUSQUEDA BINARIA EN UN VECTOR ORDENADO:");

  /*  Relleno aleatorio  de los  100 componentes  del vector. A cada
  componente se le  asigna un valor equivalente al  doble del índice
  que  ocupan  en   el  vector.  A  la  variable   x  se  le  asigna
  arbitrariamente la mitad de lo que vale la variable i al salir del
  bucle. */

  for (i = 0; i <= 99; i++)
    vector[i] = i * 2;
  x = i / 2;

  /* Escritura en pantalla del vector ordenado y valor a buscar. */
  printf ("\n\nVector:\n");
  for (i = 0; i < 100; i++)
    printf ("%d\t", vector[i]);
  printf ("\nValor a buscar: %d", x);

  /* Búsqueda binaria en vector ordenado. */
  encontrado = 0;
  izquierda = 0;
  derecha = 99;
  while (! encontrado && izquierda <= derecha)
    {
      centro = (izquierda + derecha) / 2;
      if (x < vector[centro])
        derecha = centro - 1;
      else if (x > vector[centro])
        izquierda = centro + 1;
      else
        encontrado = 1;
    }

  /* Escritura en pantalla del vector ordenado. */
  if (encontrado)
    printf ("\n\nValor %d encontrado en índice %d (recordar que"
            " empieza en 0).", x, centro);
  else
    printf ("\n\nNo existe el valor %d en el vector.", x);
  /* Espera la pulsación de la tecla RETURN para finalizar el
  programa. */
  getch ();
}