Рубрики

Java-программа для бинарного поиска (рекурсивная и итеративная)

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

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

// 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);

    }

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

Выход:

Element found at index 3

// 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);

    }

}

Выход:

Element found at index 3

Пожалуйста, обратитесь к полной статье о бинарном поиске для более подробной информации!

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

Java-программа для бинарного поиска (рекурсивная и итеративная)

0.00 (0%) 0 votes