Căutarea binară

Aspecte teoretice:

Algoritmul de căutare binară este un algoritm de căutare folosit pentru a găsi un element într-o listă ordonată (tablou unidimensional/vector). Algoritmul funcționează pe baza tehnicii divide et impera. Valoarea căutată este comparată cu cea a elementului din mijlocul listei. Dacă e egală cu cea a acelui element, algoritmul se termină. Dacă e mai mare decât acea valoare, algoritmul se reia, de la mijlocul listei până la sfârșit, iar dacă e mai mică, algoritmul se reia pentru elementele de la începutul listei până la mijloc. Întrucât la fiecare pas cardinalul mulțimii de elemente în care se efectuează căutarea se înjumătățește, algoritmul are complexitate logaritmică.

Se consideră un tablou unidimensional v de n elemente deja sortat și trei variabile: i=inceput, s=sfârșit și m=mijloc. Metoda verifică de mai multe ori dacă mijlocul vectorului/tabloului unidimensional este egal cu elementul căutat:
în cazul în care este egală, variabila m reprezintă poziția elementului în vector;
dacă nu se îndeplinește condiția de egalitate se trece la verificarea poziției elementului căutat în vector astfel: dacă elementul căutat este mai mic decât elementul din mijlocul vectorului, variabila “s” ia valoarea lui “m” iar dacă nu variabila i ia valoarea lui m.

Totul se repetă atât timp cât i este mai mic decât s. Complexitate: O(n*log n)

Implementare:

Cod Sursa C#

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
 
namespace CautareBinaraCS
{
    class Program
    {
        static int cautare(int stanga, int dreapta, int x, int[] v)
        {
            int mijloc;
            //int x;
            if (stanga > dreapta)
                return -1;
            else
            {
                mijloc = (stanga + dreapta) / 2;
                if (x == v[mijloc])
                    return mijloc;
                if (x < v[mijloc])
                    return cautare(stanga, mijloc - 1, x, v);
                else
                    return cautare(mijloc + 1, dreapta, x, v);
            }
        }
        static void Main(string[] args)
        {
            int n, x, i;
            int[] v = new int[20];
            Console.Write("numarul elementelor n= ");
            n = Convert.ToInt32(Console.ReadLine());
            Console.Write("numarul cautat x= ");
            x = Convert.ToInt32(Console.ReadLine());
            Console.WriteLine("Dati " + n + "elemente(in ordine crescatoare)");
            for (i = 1; i <= n; i++)
            {
                Console.Write("v[" + i + "]=");
                v[i] = Convert.ToInt32(Console.ReadLine());
            }
            Console.WriteLine("Elementul " + x + " a fost gasit pe pozitia: " + cautare(1, n, x, v));
            Console.ReadKey();
        }
    }
}

Cod Sursa VB

Module Module1
    Dim v(20) As Integer
    Dim n, x, mijloc As Integer
 
    Function Cautare(ByVal stanga As Integer, ByVal dreapta As Integer) As Integer
        If stanga > dreapta Then
            Return -1
        Else
            mijloc = (stanga + dreapta) / 2
            If x = v(mijloc) Then
                Return mijloc
            End If
            If x < v(mijloc) Then
                Return Cautare(stanga, mijloc - 1)
            Else
                Return Cautare(mijloc + 1, dreapta)
            End If
        End If
    End Function
 
    Sub Main()
        Console.Write("numarul elementelor n= ")
        n = Convert.ToInt32(Console.ReadLine())
        Console.Write("numarul cautat x= ")
        x = Convert.ToInt32(Console.ReadLine())
        Console.WriteLine("dati " & n & "elemente (in ordine crescatoare) ")
        For i = 1 To n
            Console.Write("v[" & i & "]=")
            v(i) = Convert.ToInt32(Console.ReadLine())
        Next i
        Console.Write("Elementul " & x & " a fost gasit pe pozitia: " & Cautare(1, n))
        Console.ReadLine()
    End Sub
 
End Module

Cod Sursa C++

#include "stdafx.h"
#include<iostream>
#include <conio.h>
 
using namespace std;
 
int n,x,v[10],mijloc;
 
int cautare (int stanga, int dreapta)
{
	if(stanga>dreapta)
		return -1;
	else
		{
			mijloc =(stanga+dreapta)/2;
			if (x==v[mijloc])
				return mijloc;
			if (x<v[mijloc])
				return cautare(stanga,mijloc-1);
			else
				return cautare(mijloc+1,dreapta);
		}
}
int main()
{   
	cout<<"numarul elementelor n= ";
	cin>>n;
	cout<<"numarul cautat x=";
	cin>>x;
	cout<<"dati "<<n<<" elemente (in ordine crescatoare).\n";
	for (int i=1;i<=n;i++)
	{
		cout<<"v["<<i<<"]=";
		cin>>v[i];
	}
	cout<<"elementul "<<x<<" a fost gasit pe pozitia: "<<cautare (1,n);
	system("pause");
}

Cod Sursa JAVA

 

//Complexitate: O(n*log n) import java.io.*; class CautareBinara {   public static int cautare(int stanga, int dreapta, int x, int v[])         {             int mijloc;             //int x;             if (stanga > dreapta)                 return –1;             else             {                 mijloc = (stanga + dreapta) / 2;                 if (x == v[mijloc])                     return mijloc;                 if (x < v[mijloc])                     return cautare(stanga, mijloc – 1, x, v);                 else                     return cautare(mijloc + 1, dreapta, x, v);             }         }     public static void main(String args[])   {     String line = null;     int x=0;     int a[]={1,3,5,7,9};     int I;     System.out.println(“Dati elementul x “);     try     {         BufferedReader is = new BufferedReader(new InputStreamReader(System.in));         line = is.readLine();         x = Integer.parseInt(line);       }       catch (NumberFormatException ex)       {         System.err.println(“Not a valid number: ” + line);       }       catch (IOException e)       {         System.err.println(“Unexpected IO ERROR: ” + e);       }     //for (i=0;i<10;i++)     System.out.println(“elementul ” + x + ” a fost gasit pe pozitia ” + cautare(1,5,x,a));   } }

Rezultat: