Левый и правый двоичный поиск

@Itachil · Регистрация: 14.10.2019

Студворк — интернет-сервис помощи студентам

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

Входные данные
В первой строке входных данных записано два числа N и M (0 < N, M < 20000 ). Во второй строке записано N упорядоченных по неубыванию целых чисел — элементы первого списка. В третьей строке записаны M целых неотрицательных чисел - элементы второго списка. Все числа в списках - целые 32-битные знаковые.

Выходные данные
Программа должна вывести M строчек. Для каждого числа из второго списка нужно вывести номер его первого и последнего вхождения в первый список. Нумерация начинается с единицы. Если число не входит в первый список, нужно вывести одно число 0.

Ввод:
10 5
1 1 3 3 5 7 9 18 18 57
57 3 9 1 179
Вывод:
10 10
3 4
7 7
1 2
0

Ввод
1 1
0
0
Вывод
1 1

вот мой код

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
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 = 0;
        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) {
                index = mid + 1;
                return key + " " + index;
            }
        }
       return "0";
    }
 
}

1)как искать последний одинаковый элемент?
2)я не понял как работает 2 ввод данных

Добавлено через 6 минут

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
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[k];
        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 = 0;
        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) {
                index = mid + 1;
                return key + " " + index;
            }
        }
       return "0";
    }
 
}

@Aviz__ · 09.02.2020, 14:16

Itachil, подсказка))

Java
1
2
3
4
5
6
7
8
9
10
11
import java.util.Scanner;
 
public class Helper {
 
    public static void main (String[] args){
        Scanner scanner = new Scanner(System.in);
        String first = scanner.nextLine();
        String second = scanner.nextLine();
        for (String tmp : second.trim().split(" "))
            System.out.println(first.indexOf(tmp) + " " + first.lastIndexOf(tmp));
    }

@Itachil · 09.02.2020, 14:25 **[ТС]**

можете подробнее рассказать что там происходить?

@Aviz__ · 09.02.2020, 14:35

Сообщение от Itachil

что там происходить?

https://docs.oracle.com/javase... tring.html

@Itachil · 09.02.2020, 14:49 **[ТС]**

как это может помочь? там ведь описание класса String

@Aviz__ · 09.02.2020, 15:16

Сообщение от Itachil

класса String

а это indexOf его метод)). следовательно, на вопрос

Сообщение от Itachil

что там происходить?

отвечают они, методы.

@Itachil · 09.02.2020, 15:50 **[ТС]**

но ведь indexOf возвращает индекс, под которым символ или строка первый раз появляется в строке. Что делать если там несколько одинаковых чисел и нужно последнее число, которое появилось

@Aviz__ · 09.02.2020, 16:56

Itachil, это аллегория, а не решение. оно может натолкнуть на решение))

Сообщение от Itachil

последнее число, которое появилось

lastIndexOf

Itachil, собственно в строках, решение вот))

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import java.util.Scanner;
 
public class Helper {
 
    public static void main (String[] args){
        Scanner scanner = new Scanner(System.in);
        String [] strArr = scanner.nextLine().trim().split(" ");
        String second = scanner.nextLine();
        for (String tmp : second.trim().split(" ")) {
            for (int i = 0; i < strArr.length; i++) {
                if (tmp.equals(strArr[i])){
                    System.out.print((i + 1) + " ");
                    break;
                }
            }
            for (int i = strArr.length - 1; i >= 0 ; i--) {
                if (tmp.equals(strArr[i])){
                    System.out.println(i + 1);
                    break;
                }
            }
        }
    }
}

резулт:

Кликните здесь для просмотра всего текста

1 1 3 3 5 7 9 18 18 57
57 3
10 10
3 4

Новые блоги и статьи Все статьи Все блоги /
Новый CodeBlocs. Версия 25.03 palva 04.01.2026 Оказывается, недавно вышла новая версия CodeBlocks за номером 25. 03. Когда-то давно я возился с только что вышедшей тогда версией 20. 03. С тех пор я давно снёс всё с компьютера и забыл. Теперь. . .	Модель микоризы: классовый агентный подход anaschu 02.01.2026 Раньше это было два гриба и бактерия. Теперь три гриба, растение. И на уровне агентов добавится между грибами или бактериями взаимодействий. До того я пробовал подход через многомерные массивы,. . .	Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Programma_Boinc 28.12.2025 Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Налог на собак: https:/ / ********/ gallery/ V06K53e Финансовый отчет в Excel: https:/ / ********/ gallery/ bKBkQFf Пост отсюда. . .	Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США. Programma_Boinc 26.12.2025 Нашел на реддите интересную статью под названием Anyone know where to get a free Desktop or Laptop? Ниже её машинный перевод. После долгих разбирательств я наконец-то вернула себе. . .	Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка. Programma_Boinc 23.12.2025 Рецензия / Мнение/ Перевод Нашел на реддите интересную статью под названием The Thinkpad X220 Tablet is the best budget school laptop period . Ниже её машинный перевод. Thinkpad X220 Tablet —. . .
PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Как объединить две одинаковые БД Access с разными данными VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .

@Itachil 0 / 0 / 0 Регистрация: 14.10.2019 Сообщений: 39
	09.02.2020, 14:25 [ТС]
	можете подробнее рассказать что там происходить? 0

@Itachil 0 / 0 / 0 Регистрация: 14.10.2019 Сообщений: 39
	09.02.2020, 14:49 [ТС]
	как это может помочь? там ведь описание класса String 0

@Itachil 0 / 0 / 0 Регистрация: 14.10.2019 Сообщений: 39
	09.02.2020, 15:50 [ТС]
	но ведь indexOf возвращает индекс, под которым символ или строка первый раз появляется в строке. Что делать если там несколько одинаковых чисел и нужно последнее число, которое появилось 0