Búsqueda – Binaria

Enunciado

Este método se aplica a una estructura ordenada y se basa en cercar al elemento buscado determinando sucesivamente la mitad del vector en que es más probable que se encuentre.

Video: Búsqueda Binaria

Código

Python

def Binary( v, k ):
    i = 0
    j = len( v )-1
    p = ( i+j )//2
    
    while i<=j and v[p]!=k:
        if k>v[p]:
            i = p+1
        else:
            j = p-1
            
        p = ( i+j )//2
        
    if i>j: p = -1
    
    return p

def main ():
    n = 5
    v1 = [ ]
    print( "Ingresar 5 numeros ordenados ", end="" )
    print( "ascendentemente/", end="" )
    print( "enter 5 numbers in ascending order: " )
    for i in range( n ):
        v1.append( int( input( ) ) )
    print()
    while True:
        print( "Ingresar numero a buscar/", end="" )
        print( "Enter number to search: ", end="" )
        num = int( input( ) )

        p = Binary( v1, num )

        if p!=-1:
            print( "\nIndice/Index: ", p, "\n" )
        else:
            print( "\nNumero inexistente/", end="" )
            print( "Non-existent number\n" )
        print()
        print( "Presione S para salir, ", end="" )
        print( "cualquier tecla para nueva consulta" )
        print( "Press S to exit, ", end="" )
        print( "any key to new query\n" )
        r = input( ).upper()
        if r=="S": break
main()

C++

#include <iostream>
#include <iomanip>
using namespace std ;
#include <conio.h>

void Binary( int n , float v[ ] , float k , int* p )
{
   int i, j ;

   i = 0 ; j = n ; *p = ( i + j ) / 2 ;
   while (i <= j && k != v[ *p ] )
   {
      if ( k < v[ *p ] ) j = *p - 1 ; else i = *p + 1 ;
      *p = ( i + j ) / 2 ;
   }
   if ( k != v[ *p ] ) *p = -1 ;
}


int main()
{
   int  i, p, n=5 ;
   float v1[20], num ;
	
   cout << "Ingresar 5 numeros ordenados " ;
   cout << "ascendentemente/" << endl ;
   cout << "enter 5 numbers in ascending order: " ;
   cout << endl ;
   for (i=0; i<n; i++)
       cin >> v1[i] ;
   cout << endl ;
   do
   {
       cout << "Ingresar numero a buscar/" ;
       cout << "Enter number to search: " ;
       cin >> num ;

       Binary( n, v1, num, &p ) ;

       if ( p!=-1 )
           cout << endl << "Indice/Index: " 
		<< p << endl ;
       else
       {
	   cout << endl 
		<< "Numero inexistente/" ;
	   cout << "Non-existent number" << endl ;
       }
       cout << endl ;
       cout << "Presione ESC para salir, " ;
       cout << "cualquier tecla para nueva consulta" 
            << endl ;
       cout << "Press ESC to exit, " << endl ;
       cout << "any key to new query" ;
       cout << endl << endl ;
   } while( getch() != char (27) ) ;
   return 0 ;
}

Pascal

Program Problema03 ;
uses CRT ;
const
    n = 5 ;
type
    dim = 0..12 ;
    vector = array [dim] of integer ;
    element = integer ;
var
    v1: vector ;
    num: element ;
    p, i: dim ;

Procedure Binary( n: dim; var v: vector; 
                  k: element; var p: dim ) ;
var
     i, j: dim ;
begin
     i := 1 ; j := n ;
     p := (i + j) div 2 ;
     while ( i<=j ) and ( v[p] <> k ) do
     begin
          if k<v[p] then j := p - 1
                    else i := p + 1 ;
          p := (i + j) div 2 ;
     end;
     if k <> v[p] then p := 0 ;
end ;

begin
    ClrScr ;
    write( 'Ingresar 5 numeros ordenados ' ) ;
    write( 'ascendentemente/' ) ;
    writeln( 'Enter 5 numbers in ascending order: ' ) ;
    for i:=1 to n do
    begin
         readln( v1[i]) ;
    end ;
    writeln ;

    repeat
          write( 'Ingresar numero a buscar/' ) ; 
          write( 'Enter number to search: ' ) ;
          readln( num ) ;
          writeln ;

          Binary( n, v1, num, p ) ;

          if p<>0
          then
              writeln( 'Posicion/Position: ', p)
          else
          begin
              write( 'Numero inexistente/' ) ;
              writeln( 'Non-existent number' ) ;
          end ;
          writeln ;
          write( 'Presione ESC para salir, ' ) ;
          write( 'cualquier tecla para ' ) ;
          writeln( 'nueva consulta' ) ;
          write( 'Press ESC to exit, ' ) ;
          writeln( 'any key to new query' ) ;
          writeln ;
    until readkey=#27 ;
end.

Diagramas