Двоично търсене

от Уикипедия, свободната енциклопедия
Направо към: навигация, търсене

Двоично търсене е алгоритъм, за намиране на елемент в предварително сортиран масив.За разлика от последователното търсене при двоичното търсене са необходими много по малко стъпки за намиране на търсения елемент.Максималният брой стъпки необходими на алгоритъма за намирането на елемент в сортиран масив е двоичен логаритъм от дължината на масива. Тоест за намиране на елемент в сортиран масив от 1 милион елемента алгоритъма ще извърши най-много 20 стъпки.

Алгоритъм[редактиране | edit source]

Алгоритъма за намиране на елемент при двоично търсене е следният:

  1. Взима средния елемент на масива.
  2. Ако средният елемент е търсената стойност, алгоритъма завършва.

В противен случай има 2 варианта:

– Търсената стойност е по-малка от средният елемент. В този случай стъпка 1 се повтаря с частта от масива преди средният елемент.
– Търсената стойност е по-голяма от средният елемент. В този случай стъпка 1 се повтаря с частта от масива след средният елемент.

Алгоритъма завършва при следните случаи:

  1. Търсеният елемент е намерен.
  2. Когато са обходени елементите на масива по описания по горе алгоритъм и търсения елемент не е намерен.В този случай може да заключим, че търсеният елемент го няма в масива.

Примери[редактиране | edit source]

С цикъл[редактиране | edit source]

C#[редактиране | edit source]

int binarySearch(int array[], int value, int left, int right)
{
    while (left <= right)
    {
        int middle = (left + right) / 2;
        if (array[middle] == value)
        {
            return middle;
        }
        else if (array[middle] > value)
        {
            right = middle - 1;
        }
        else
        {
            left = middle + 1;
        }
     }
     return -1;
}

Visual Basic[редактиране | edit source]

Function BinarySearch(ByVal A() As Integer, ByVal value As Integer) As Integer
    Dim low As Integer = 0
    Dim high As Integer = A.Length - 1
    Dim middle As Integer = 0
 
    While low <= high
        middle = (low + high) / 2
        If A(middle) > value Then
            high = middle - 1
        ElseIf A(middle) < value Then
            low = middle + 1
        Else
            Return middle
        End If
    End While
 
    Return Nothing
End Function

Рекурсивно[редактиране | edit source]

C#[редактиране | edit source]

static int BinarySearchRecursive(int[] array, int value, int low, int high)
{
    if (high < low)
    {
        return -1;
    }
    int middle = (low + high) / 2;
    if (array[middle] > value)
    {
        return BinarySearchRecursive(array, value, low, middle - 1);
    }
    else if (array[middle] < value)
    {
        return BinarySearchRecursive(array, value, middle + 1, high);
    }
    else
    {
        return middle;
    }
}

Visual Basic[редактиране | edit source]

Function BinarySearch(ByVal A() As Integer, ByVal value As Integer, ByVal low As Integer, ByVal high As Integer) As Integer
    Dim middle As Integer = 0
 
    If high < low Then
        Return Nothing
    End If
 
    middle = (low + high) / 2
 
    If A(middle) > value Then
        Return BinarySearch(A, value, low, middle - 1)
    ElseIf A(middle) < value Then
        Return BinarySearch(A, value, middle + 1, high)
    Else
        Return middle
    End If
End Function

Източници[редактиране | edit source]