Question

Реализуйте алгоритм бинарного поиска. Входные данные В первой строке входных данных содержатся натуральные числа N и K (0 < N, K < 20000). Во второй строке задаются N элементов первого массива, отсортированного по возрастанию, а в третьей строке – K элементов второго массива. Элементы обоих массивов - целые числа, каждое из которых по модулю не превосходит 109 Выходные данные Требуется для каждого из K чисел вывести в отдельную строку "YES", если это число встречается в первом массиве, и "NO" в противном случае.

Answer 1

Ответ:

import java.util.Arrays;

import java.util.Scanner;

public class Main {

   public static void main(String[] args) {

       Scanner in = new Scanner(System.in);

       int n = in.nextInt();

       int k = in.nextInt();

       int[] array = new int[n];

       int[] array1 = new int[n];

       for (int i = 0;i < array.length;i++){

           array[i] = in.nextInt();

       }

       for (int i = 0;i < k;i++){

          array1[i] = in.nextInt();

           System.out.println(binarySearch(array,array1[i]));

       }

        }

   static String binarySearch(int[] sortedArray, int key) {

       int index = -1;

       int low = 0;

       int high = sortedArray.length - 1;

       while (low <= high) {

           int mid = (low + high) / 2;

           if (sortedArray[mid] < key) {

               low = mid + 1;

           } else if (sortedArray[mid] > key) {

               high = mid - 1;

           } else if (sortedArray[mid] == key) {

              return "YES";

           }

       }

       return "NO";

   }

}

Объяснение:

Answer 2

Для реализации алгоритма бинарного поиска, который позволит эффективно находить элементы в отсортированном массиве, выполним следующие шаги:

1. Считаем входные данные: число N и K, элементы первого и второго массивов.
2. Реализуем функцию бинарного поиска для нахождения элемента в отсортированном массиве.
3. Проходим по второму массиву и для каждого элемента выполняем бинарный поиск в первом массиве.
4. Выводим "YES", если элемент найден, и "NO" в противном случае.

Вот Python-код, реализующий описанный алгоритм:

pythonCopy code
def binary_search(arr, target):
    left, right = 0, len(arr) - 1

    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return True
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return False

def main():
    # Чтение входных данных
    N, K = map(int, input().split())
    first_array = list(map(int, input().split()))
    second_array = list(map(int, input().split()))

    # Для каждого элемента второго массива выполняем бинарный поиск в первом массиве
    for num in second_array:
        if binary_search(first_array, num):
            print("YES")
        else:
            print("NO")

if __name__ == "__main__":
    main()

Пример входных данных:

Copy code
5 3
1 3 5 7 9
2 4 8

Пример вывода:

objectivecCopy code
NO
NO
YES

Помните, что данный код предполагает, что оба массива уже отсортированы по возрастанию, что является обязательным условием для использования бинарного поиска.