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";

   }

}

Объяснение: