Continuando con los métodos de búsqueda, seguimos con la búsqueda binaria. Este método es el que habitualmente utilizamos los humanos para encontrar un determinado elemento en una lista previamente ordenada.

El algoritmo es el siguiente:

  1. Se compara el valor buscado con el del elemento central del vector
    • Si coinciden, se ha encontrado el numero y se finaliza la búsqueda.
    • Si no coinciden, se determina si el valor buscado debe estar en la mitad izquierda o derecha del vector, dependiendo de si es inferior o superior, respectivamente, del elemento central.

La posición del elemento central del vector es calculado con la siguiente formula:

pMitad = int((pInicial + pFinal)/2)

Donde pInicial y pFinal son las posiciones inicial y final del subVector que se está considerando.

  1. En la mitad donde se deba continuar la búsqueda, se continua de la misma manera, es decir; se compara el valor buscado con el elemento central de esa mitad.
    • Si coinciden, se ha encontrado el numero y se finaliza la búsqueda.
    • Si no coinciden, se determina en cúal de las dos mitades de esta subMitad debe estar el valor buscado.
  1. Se continua de este modo (dividiendo el vector en subMitades) hasta que la búsqueda:
    • Finalice con exito (se encuentre el elemento)
    • Se finalice sin exito (no se encontro el elemento)
  1. Cuando pInicial sea mayor o igual a pFinal y su contenido sea diferente del valor buscado, entonces se considera que el valor buscado no existe en el vector.

Este es el algoritmo:
Click para agrandar

Aquí está el código en VB.Net

PLAIN TEXT
VB.NET:
  1. Public Class Form1
  2.     Dim vec(999) As Integer
  3.     Dim a As Integer
  4.  
  5.     Private Function quicksort(ByVal vec() As Integer, ByVal primero As Integer, ByVal ultimo As Integer) As Array
  6.         Dim a, b, piv, Npiv, aux As Integer
  7.         piv = vec(primero) 'sacamos pivote
  8.         Npiv = primero
  9.  
  10.         For a = primero To ultimo
  11.             If a <> Npiv Then 'si el pivote no se esta queriendo comparar con el mismo pivote
  12.                 If vec(a) <piv Then
  13.                     'mandamos los numeros a la izquierda
  14.                     aux = vec(a)
  15.  
  16.                     'recorremos sub-vector (desde piv hasta vec(a))
  17.                     For b = a To Npiv + 1 Step -1
  18.                         vec(b) = vec(b - 1)
  19.                     Next
  20.  
  21.                     vec(Npiv) = aux   'colocamos numero menor a la izquierda de piv
  22.                     Npiv += 1         'actualizamos posicion de piv
  23.                 End If
  24.             End If
  25.         Next
  26.  
  27.         'enviamos recursivamente el vector a la izuierda de piv
  28.         If (Npiv - primero <> 0) Then 'si el sub-vector de la izquierda tiene elementos, entonces se hace recursividad
  29.             vec = quicksort(vec, primero, Npiv - 1)
  30.         End If
  31.  
  32.         'enviamos recursivamente el vector a la derecha de piv
  33.         If (ultimo - Npiv <> 0) Then 'si el sub-vector de la derecha tiene elementos, entonces se hace recursividad
  34.             vec = quicksort(vec, Npiv + 1, ultimo)
  35.         End If
  36.  
  37.         Return vec
  38.     End Function
  39.  
  40.     Private Sub Form1_Load(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles MyBase.Load
  41.         Dim rand As New Random
  42.         Dim cad As String = ""
  43.  
  44.         For a = 0 To 999
  45.             vec(a) = rand.Next(0, 4000)
  46.         Next
  47.  
  48.         quicksort(vec, 0, vec.Length - 1)
  49.  
  50.         For a = 0 To 999
  51.             cad &= vec(a) & vbNewLine
  52.         Next
  53.         txt.Text = cad
  54.     End Sub
  55.  
  56.     Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button1.Click
  57.         Dim I, D, P, N, band As Integer
  58.         N = txtn.Text
  59.         band = 0
  60.         I = 0
  61.         D = vec.Length - 1
  62.         r.Text = ""
  63.  
  64.         While (I <= D And D <= vec.Length - 1 And I <= vec.Length - 1 And band = 0)
  65.             P = CType((I + D) / 2, Integer)
  66.             If (vec(P) = N) Then
  67.                 band = 1
  68.                 r.Text = N & " fue encontrado en la posición " & P
  69.             Else
  70.                 If (N <vec(P)) Then
  71.                     D = P - 1
  72.                 Else
  73.                     I = P + 1
  74.                 End If
  75.             End If
  76.         End While
  77.  
  78.         If (r.Text.Length = 0) Then r.Text = "# no encontrado"
  79.     End Sub
  80. End Class

Aquí te dejo el archivo completo para que te lo descargues ;)

Descarga

Saludos!

Fuente del algoritmo