Рубрики

Бинарный поиск

Учитывая отсортированный массив arr [] из n элементов, напишите функцию для поиска заданного элемента x в arr [].

Простой подход — выполнить линейный поиск . Временная сложность вышеприведенного алгоритма составляет O (n). Другой подход для выполнения той же задачи — использование бинарного поиска.

Бинарный поиск: поиск отсортированного массива путем многократного деления интервала поиска пополам. Начните с интервала, охватывающего весь массив. Если значение ключа поиска меньше, чем элемент в середине интервала, сузьте интервал до нижней половины. В противном случае сузьте его до верхней половины. Повторно проверяйте, пока значение не будет найдено или интервал не будет пустым.

Пример :

Идея бинарного поиска состоит в том, чтобы использовать информацию о том, что массив отсортирован, и сократить временную сложность до O (Log n).

Мы в основном игнорируем половину элементов сразу после одного сравнения.

  1. Сравните х со средним элементом.
  2. Если x соответствует среднему элементу, мы возвращаем средний индекс.
  3. Иначе Если x больше среднего элемента, то x может находиться только в правой половине подрешетки после среднего элемента. Таким образом, мы вернемся к правой половине.
  4. Остальное (х меньше) повторяется для левой половины.

Рекурсивная реализация бинарного поиска

С

// C программа для реализации рекурсивного бинарного поиска
#include <stdio.h>

  
// Рекурсивная функция двоичного поиска. Возвращается
// расположение x в заданном массиве arr [l..r] присутствует,
// иначе -1

int binarySearch(int arr[], int l, int r, int x)

{

    if (r >= l) {

        int mid = l + (r - l) / 2;

  

        // Если элемент присутствует посередине

        // сам

        if (arr[mid] == x)

            return mid;

  

        // Если элемент меньше среднего, то

        // он может присутствовать только в левом подмассиве

        if (arr[mid] > x)

            return binarySearch(arr, l, mid - 1, x);

  

        // иначе элемент может присутствовать только

        // в правом подмассиве

        return binarySearch(arr, mid + 1, r, x);

    }

  

    // Мы достигаем здесь, когда элемент не

    // присутствует в массиве

    return -1;

}

  

int main(void)

{

    int arr[] = { 2, 3, 4, 10, 40 };

    int n = sizeof(arr) / sizeof(arr[0]);

    int x = 10;

    int result = binarySearch(arr, 0, n - 1, x);

    (result == -1) ? printf("Element is not present in array")

                   : printf("Element is present at index %d",

                            result);

    return 0;

}

C ++

// C ++ программа для реализации рекурсивного бинарного поиска
#include <iostream>

using namespace std;

  
// Рекурсивная функция двоичного поиска. Возвращается
// расположение x в заданном массиве arr [l..r] присутствует,
// иначе -1

int binarySearch(int arr[], int l, int r, int x)

{

    if (r >= l) {

        int mid = l + (r - l) / 2;

  

        // Если элемент присутствует посередине

        // сам

        if (arr[mid] == x)

            return mid;

  

        // Если элемент меньше среднего, то

        // он может присутствовать только в левом подмассиве

        if (arr[mid] > x)

            return binarySearch(arr, l, mid - 1, x);

  

        // иначе элемент может присутствовать только

        // в правом подмассиве

        return binarySearch(arr, mid + 1, r, x);

    }

  

    // Мы достигаем здесь, когда элемент не

    // присутствует в массиве

    return -1;

}

  

int main(void)

{

    int arr[] = { 2, 3, 4, 10, 40 };

    int x = 10;

    int n = sizeof(arr) / sizeof(arr[0]);

    int result = binarySearch(arr, 0, n - 1, x);

    (result == -1) ? cout << "Element is not present in array"

                   : cout << "Element is present at index " << result;

    return 0;

}

Джава

// Java-реализация рекурсивного бинарного поиска

class BinarySearch {

    // Возвращает индекс x, если он присутствует в arr [l ..

    // r], иначе вернем -1

    int binarySearch(int arr[], int l, int r, int x)

    {

        if (r >= l) {

            int mid = l + (r - l) / 2;

  

            // Если элемент присутствует в

            // середина

            if (arr[mid] == x)

                return mid;

  

            // Если элемент меньше среднего, то

            // он может присутствовать только в левом подмассиве

            if (arr[mid] > x)

                return binarySearch(arr, l, mid - 1, x);

  

            // иначе элемент может присутствовать только

            // в правом подмассиве

            return binarySearch(arr, mid + 1, r, x);

        }

  

        // Мы достигаем здесь, когда элемента нет

        // в массиве

        return -1;

    }

  

    // Метод драйвера для тестирования выше

    public static void main(String args[])

    {

        BinarySearch ob = new BinarySearch();

        int arr[] = { 2, 3, 4, 10, 40 };

        int n = arr.length;

        int x = 10;

        int result = ob.binarySearch(arr, 0, n - 1, x);

        if (result == -1)

            System.out.println("Element not present");

        else

            System.out.println("Element found at index " + result);

    }

}
/ * Этот код предоставлен Раджатом Мишрой * /

питон

# Программа Python для рекурсивного бинарного поиска.

  
# Возвращает индекс x в arr, если присутствует, иначе -1

def binarySearch (arr, l, r, x):

  

    # Проверьте базовый случай

    if r >= l:

  

        mid = l + (r - l)/2

  

        # Если элемент присутствует в самой середине

        if arr[mid] == x:

            return mid

          

        # Если элемент меньше середины, то он

        # может присутствовать только в левом подмассиве

        elif arr[mid] > x:

            return binarySearch(arr, l, mid-1, x)

  

        # Иначе элемент может присутствовать только

        # в правом подмассиве

        else:

            return binarySearch(arr, mid + 1, r, x)

  

    else:

        # Элемент отсутствует в массиве

        return -1

  
# Тестовый массив

arr = [ 2, 3, 4, 10, 40 ]

x = 10

  
# Вызов функции

result = binarySearch(arr, 0, len(arr)-1, x)

  

if result != -1:

    print "Element is present at index % d" % result

else:

    print "Element is not present in array"

C #

// C # реализация рекурсивного бинарного поиска

using System;

  

class GFG {

    // Возвращает индекс х, если он присутствует в

    // arr [l..r], иначе вернуть -1

    static int binarySearch(int[] arr, int l,

                            int r, int x)

    {

        if (r >= l) {

            int mid = l + (r - l) / 2;

  

            // Если элемент присутствует в

            // середина

            if (arr[mid] == x)

                return mid;

  

            // Если элемент меньше среднего, то

            // он может присутствовать только в левом подмассиве

            if (arr[mid] > x)

                return binarySearch(arr, l, mid - 1, x);

  

            // иначе элемент может присутствовать только

            // в правом подмассиве

            return binarySearch(arr, mid + 1, r, x);

        }

  

        // Мы достигаем здесь, когда элемента нет

        // в массиве

        return -1;

    }

  

    // Метод драйвера для тестирования выше

    public static void Main()

    {

  

        int[] arr = { 2, 3, 4, 10, 40 };

        int n = arr.Length;

        int x = 10;

  

        int result = binarySearch(arr, 0, n - 1, x);

  

        if (result == -1)

            Console.WriteLine("Element not present");

        else

            Console.WriteLine("Element found at index "

                              + result);

    }

}

  
// Этот код предоставлен Sam007.

PHP

<?php
// PHP-программа для реализации
// рекурсивный бинарный поиск

  
// Рекурсивный бинарный поиск
// функция. Возвращает местоположение
// х в данном массиве arr [l..r]
// присутствует, иначе -1

function binarySearch($arr, $l, $r, $x)

{

if ($r >= $l)

{

        $mid = ceil($l + ($r - $l) / 2);

  

        // Если элемент присутствует

        // в середине

        if ($arr[$mid] == $x

            return floor($mid);

  

        // Если элемент меньше чем

        // середина, тогда это может быть только

        // присутствует в левом подмассиве

        if ($arr[$mid] > $x

            return binarySearch($arr, $l

                                $mid - 1, $x);

  

        // иначе элемент может только

        // присутствовать в правом подмассиве

        return binarySearch($arr, $mid + 1, 

                            $r, $x);

}

  
// Мы достигаем здесь, когда элемент
// нет в массиве

return -1;

}

  
// Код драйвера

$arr = array(2, 3, 4, 10, 40);

$n = count($arr);

$x = 10;

$result = binarySearch($arr, 0, $n - 1, $x);

if(($result == -1))

echo "Element is not present in array";

else

echo "Element is present at index ",

                            $result;

                              
// Этот код предоставлен anuj_67.
?>


Выход :

Element is present at index 3

Итеративная реализация бинарного поиска

С

// C программа для реализации итеративного бинарного поиска
#include <stdio.h>

  
// Итеративная функция двоичного поиска. Возвращается
// расположение x в заданном массиве arr [l..r], если присутствует,
// иначе -1

int binarySearch(int arr[], int l, int r, int x)

{

    while (l <= r) {

        int m = l + (r - l) / 2;

  

        // Проверяем, присутствует ли х в середине

        if (arr[m] == x)

            return m;

  

        // Если х больше, игнорируем левую половину

        if (arr[m] < x)

            l = m + 1;

  

        // Если х меньше, игнорируем правую половину

        else

            r = m - 1;

    }

  

    // если мы достигнем здесь, то элемент был

    // нет

    return -1;

}

  

int main(void)

{

    int arr[] = { 2, 3, 4, 10, 40 };

    int n = sizeof(arr) / sizeof(arr[0]);

    int x = 10;

    int result = binarySearch(arr, 0, n - 1, x);

    (result == -1) ? printf("Element is not present"

                            " in array")

                   : printf("Element is present at "

                            "index %d",

                            result);

    return 0;

}

C ++

// C ++ программа для реализации рекурсивного бинарного поиска
#include <iostream>

using namespace std;

  
// Итеративная функция двоичного поиска. Возвращается
// расположение x в заданном массиве arr [l..r], если присутствует,
// иначе -1

int binarySearch(int arr[], int l, int r, int x)

{

    while (l <= r) {

        int m = l + (r - l) / 2;

  

        // Проверяем, присутствует ли х в середине

        if (arr[m] == x)

            return m;

  

        // Если х больше, игнорируем левую половину

        if (arr[m] < x)

            l = m + 1;

  

        // Если х меньше, игнорируем правую половину

        else

            r = m - 1;

    }

  

    // если мы достигнем здесь, то элемент был

    // нет

    return -1;

}

  

int main(void)

{

    int arr[] = { 2, 3, 4, 10, 40 };

    int x = 10;

    int n = sizeof(arr) / sizeof(arr[0]);

    int result = binarySearch(arr, 0, n - 1, x);

    (result == -1) ? cout << "Element is not present in array"

                   : cout << "Element is present at index " << result;

    return 0;

}

Джава

// Java реализация итеративного бинарного поиска

class BinarySearch {

    // Возвращает индекс x, если он присутствует в arr [],

    // еще вернем -1

    int binarySearch(int arr[], int x)

    {

        int l = 0, r = arr.length - 1;

        while (l <= r) {

            int m = l + (r - l) / 2;

  

            // Проверяем, присутствует ли х в середине

            if (arr[m] == x)

                return m;

  

            // Если х больше, игнорируем левую половину

            if (arr[m] < x)

                l = m + 1;

  

            // Если х меньше, игнорируем правую половину

            else

                r = m - 1;

        }

  

        // если мы достигнем здесь, то элемент был

        // нет

        return -1;

    }

  

    // Метод драйвера для тестирования выше

    public static void main(String args[])

    {

        BinarySearch ob = new BinarySearch();

        int arr[] = { 2, 3, 4, 10, 40 };

        int n = arr.length;

        int x = 10;

        int result = ob.binarySearch(arr, x);

        if (result == -1)

            System.out.println("Element not present");

        else

            System.out.println("Element found at "

                               + "index " + result);

    }

}

питон

# Python-код для реализации итеративного двоичного кода
# Поиск.

  
# Возвращает местоположение x в указанном массиве
# если присутствует, иначе возвращает -1

def binarySearch(arr, l, r, x):

  

    while l <= r:

  

        mid = l + (r - l)/2;

          

        # Проверьте, присутствует ли х в середине

        if arr[mid] == x:

            return mid

  

        # Если х больше, игнорировать левую половину

        elif arr[mid] < x:

            l = mid + 1

  

        # Если х меньше, игнорируйте правую половину

        else:

            r = mid - 1

      

    # Если мы доберемся сюда, то элемент

    # не было

    return -1

  

  
# Тестовый массив

arr = [ 2, 3, 4, 10, 40 ]

x = 10

  
# Вызов функции

result = binarySearch(arr, 0, len(arr)-1, x)

  

if result != -1:

    print "Element is present at index % d" % result

else:

    print "Element is not present in array"

C #

// C # реализация итеративного бинарного поиска

using System;

  

class GFG {

    // Возвращает индекс x, если он присутствует в arr [],

    // еще вернем -1

    static int binarySearch(int[] arr, int x)

    {

        int l = 0, r = arr.Length - 1;

        while (l <= r) {

            int m = l + (r - l) / 2;

  

            // Проверяем, присутствует ли х в середине

            if (arr[m] == x)

                return m;

  

            // Если х больше, игнорируем левую половину

            if (arr[m] < x)

                l = m + 1;

  

            // Если х меньше, игнорируем правую половину

            else

                r = m - 1;

        }

  

        // если мы достигнем здесь, то элемент был

        // нет

        return -1;

    }

  

    // Метод драйвера для тестирования выше

    public static void Main()

    {

        int[] arr = { 2, 3, 4, 10, 40 };

        int n = arr.Length;

        int x = 10;

        int result = binarySearch(arr, x);

        if (result == -1)

            Console.WriteLine("Element not present");

        else

            Console.WriteLine("Element found at "

                              + "index " + result);

    }

}
// Этот код предоставлен Sam007

PHP

<?php
// PHP-программа для реализации
// итеративный бинарный поиск

  
// Итеративный бинарный поиск
// функция. Возвращает местоположение
// х в данном массиве arr [l..r]
// если присутствует, иначе -1

function binarySearch($arr, $l

                      $r, $x)

{

    while ($l <= $r)

    {

        $m = $l + ($r - $l) / 2;

  

        // Проверяем, присутствует ли х в середине

        if ($arr[$m] == $x)

            return floor($m);

  

        // Если х больше, игнорировать

        // левая половина

        if ($arr[$m] < $x)

            $l = $m + 1;

  

        // Если х меньше,

        // игнорируем правую половину

        else

            $r = $m - 1;

    }

  

    // если мы доберемся сюда, то

    // элемент отсутствует

    return -1;

}

  
// Код драйвера

$arr = array(2, 3, 4, 10, 40);

$n = count($arr);

$x = 10;

$result = binarySearch($arr, 0, 

                       $n - 1, $x);

if(($result == -1))

echo "Element is not present in array";

else

echo "Element is present at index "

                            $result;

  
// Этот код предоставлен anuj_67.
?>


Выход :

Element is present at index 3

Сложность времени:
Временная сложность бинарного поиска может быть записана как

T(n) = T(n/2) + c 

Вышеуказанное повторение может быть решено с использованием метода повторения Т или метода Мастера. Это относится к случаю II мастер-метода и решение повторения ,

Вспомогательное пространство: O (1) в случае итеративной реализации. В случае рекурсивной реализации, O (Logn) пространство стека рекурсивных вызовов.

Алгоритмическая парадигма: уменьшай и властвуй .

Интересные статьи на основе бинарного поиска.

Вопросы практики кодирования при бинарном поиске
Последние статьи о бинарном поиске.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Бинарный поиск

0.00 (0%) 0 votes