A shelf holds n books in increasing order of book number.
All book numbers are different, and the positions are 1, 2, …, n from the left.
To look for book number x, the librarian works as follows.
At the start, the first position to search is 1 and the last is n.
The librarian pulls out the book at the position given by the quotient of (first position + last position) divided by 2 (the remainder is dropped).
If that book's number is x, the search ends.
If that book's number is smaller than x, the first position moves to just after that position; if it is larger than x, the last position moves to just before that position.
If the first position is larger than the last after the move, the book is not there and the search ends.
Otherwise the librarian repeats the same steps with the new first and last positions and pulls out the next book.
The first line gives n and q, the second line the n book numbers, and the third line the q numbers to look for, each separated by single spaces.
For each number to look for, print on one line the numbers of the books the librarian pulled out, in order, followed by the position where it was found, separated by single spaces.
If it was not found, write 0 in place of the position.
On the shelf of the example, x = 15 is the very first book pulled out, so the line is "15 3".
Input
1 ≤ n ≤ 100, 1 ≤ q ≤ 100, 1 ≤ book number ≤ 1,000, 1 ≤ x ≤ 1,000 (all integers; book numbers are increasing and distinct)
Output
One line per number to look for: the numbers of the books pulled out, then the position found (0 if none)
Example 1 · stdin
6 5
3 8 15 20 42 77
42 8 9 77 3
stdout
15 42 5
15 3 8 2
15 3 8 0
15 42 77 6
15 3 1
main.py
Error List00F8 ↓ · ⇧F8 ↑
Input (stdin)
When you run, these lines are fed to input()/stdin in order (the program doesn't stop to ask).
$ Ready
Open this on a computer to write and run code. On mobile you can read the problem and the solutions.
In other languagesShow solutions by language · 8 languages
The way to keep only the quotient when finding the middle position differs by language. Python (lo + hi) // 2; C, C++, Java and C# (lo + hi) / 2 between ints; JS/TS Math.floor((lo + hi) / 2); Craykon Mathf.Quot(lo + hi, 2). There are also ready-made searchers. Python bisect.bisect_left, C++ std::lower_bound, Java Arrays.binarySearch and C# Array.BinarySearch give only one thing for 42 in the example: the position 4, counted from 0. They do not tell you which books were pulled out, so here you write the search yourself. Trap one: the loop condition is lo <= hi. With lo < hi the book is not pulled out when one position is left, and the fourth line of the example becomes 15 42 0. Trap two: in JS, dividing with / and no Math.floor makes the middle 3.5, and the book at that position is undefined, so every line of the example is two spaces followed by just 0. In Craykon, using / stops with an error saying the number inside [ ] must be an integer. Trap three: in Python, if the book numbers are not converted with int, they are compared as strings and "15" < "8" is true. The second line of the example becomes 15 42 77 0. Trap four: rounding the middle up with (lo + hi + 1) / 2 pulls out different books. The first line of the example becomes 20 77 42 5. Trap five: counting positions from 0 and printing that number as it is makes every position one too small. The first line of the example becomes 15 42 4, and the last line is 15 3 0, which looks like "not found" even though it was found.
Pythonmain.py · 19 lines
n, q = map(int, input().split())books = list(map(int, input().split()))queries = list(map(int, input().split()))for x in queries: lo, hi = 1, n # 아직 찾아볼 자리의 처음과 끝 seen = [] # 펼쳐 본 책 번호 answer = 0 while lo <= hi: mid = (lo + hi) // 2 # 몫만 남긴다 book = books[mid - 1] # mid번째 자리는 목록의 mid - 1번 칸 seen.append(book) if book == x: answer = mid break if book < x: lo = mid + 1 else: hi = mid - 1 print(*seen, answer)
JavaScriptmain.js · 25 lines
const lines = require("fs").readFileSync(0, "utf8").split("\n");const [n, q] = lines[0].trim().split(/\s+/).map(Number);const books = lines[1].trim().split(/\s+/).map(Number);const queries = lines[2].trim().split(/\s+/).map(Number);const out = [];for (let k = 0; k < q; k++) { const x = queries[k]; let lo = 1, hi = n; // 아직 찾아볼 자리의 처음과 끝 const seen = []; // 펼쳐 본 책 번호 let answer = 0; while (lo <= hi) { const mid = Math.floor((lo + hi) / 2); // 몫만 남긴다 const book = books[mid - 1]; // mid번째 자리는 배열의 mid - 1번 칸 seen.push(book); if (book === x) { answer = mid; break; } if (book < x) lo = mid + 1; else hi = mid - 1; } seen.push(answer); out.push(seen.join(" "));}console.log(out.join("\n"));
TypeScriptmain.ts · 26 lines
import { readFileSync } from "node:fs";const lines: string[] = readFileSync(0, "utf8").split("\n");const [n, q]: number[] = lines[0].trim().split(/\s+/).map(Number);const books: number[] = lines[1].trim().split(/\s+/).map(Number);const queries: number[] = lines[2].trim().split(/\s+/).map(Number);const out: string[] = [];for (let k = 0; k < q; k++) { const x: number = queries[k]; let lo = 1, hi = n; // 아직 찾아볼 자리의 처음과 끝 const seen: number[] = []; // 펼쳐 본 책 번호 let answer = 0; while (lo <= hi) { const mid: number = Math.floor((lo + hi) / 2); // 몫만 남긴다 const book: number = books[mid - 1]; // mid번째 자리는 배열의 mid - 1번 칸 seen.push(book); if (book === x) { answer = mid; break; } if (book < x) lo = mid + 1; else hi = mid - 1; } seen.push(answer); out.push(seen.join(" "));}console.log(out.join("\n"));
JavaMain.java · 29 lines
import java.util.Scanner;public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(), q = sc.nextInt(); int[] books = new int[n]; for (int i = 0; i < n; i++) books[i] = sc.nextInt(); StringBuilder out = new StringBuilder(); for (int k = 0; k < q; k++) { int x = sc.nextInt(); int lo = 1, hi = n; // 아직 찾아볼 자리의 처음과 끝 int answer = 0; while (lo <= hi) { int mid = (lo + hi) / 2; // int끼리 나누면 몫만 남는다 int book = books[mid - 1]; // mid번째 자리는 배열의 mid - 1번 칸 out.append(book).append(' '); if (book == x) { answer = mid; break; } if (book < x) lo = mid + 1; else hi = mid - 1; } out.append(answer).append('\n'); } System.out.print(out); }}
C#Main.cs · 37 lines
using System;using System.Text;class Program{ static void Main() { string[] head = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); int n = int.Parse(head[0]), q = int.Parse(head[1]); string[] bookParts = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); string[] queryParts = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); int[] books = new int[n]; for (int i = 0; i < n; i++) books[i] = int.Parse(bookParts[i]); var sb = new StringBuilder(); for (int k = 0; k < q; k++) { int x = int.Parse(queryParts[k]); int lo = 1, hi = n; // 아직 찾아볼 자리의 처음과 끝 int answer = 0; while (lo <= hi) { int mid = (lo + hi) / 2; // int끼리 나누면 몫만 남는다 int book = books[mid - 1]; // mid번째 자리는 배열의 mid - 1번 칸 sb.Append(book).Append(' '); if (book == x) { answer = mid; break; } if (book < x) lo = mid + 1; else hi = mid - 1; } sb.Append(answer).Append('\n'); } Console.Write(sb); }}
C++main.cpp · 27 lines
#include <iostream>#include <vector>int main() { int n, q; std::cin >> n >> q; std::vector<int> books(n); for (int i = 0; i < n; i++) std::cin >> books[i]; for (int k = 0; k < q; k++) { int x; std::cin >> x; int lo = 1, hi = n; // 아직 찾아볼 자리의 처음과 끝 int answer = 0; while (lo <= hi) { int mid = (lo + hi) / 2; // int끼리 나누면 몫만 남는다 int book = books[mid - 1]; // mid번째 자리는 vector의 mid - 1번 칸 std::cout << book << " "; if (book == x) { answer = mid; break; } if (book < x) lo = mid + 1; else hi = mid - 1; } std::cout << answer << "\n"; }}
Cmain.c · 29 lines
#include <stdio.h>int main(void) { int n, q; int books[100]; if (scanf("%d %d", &n, &q) != 2) return 0; for (int i = 0; i < n; i++) { if (scanf("%d", &books[i]) != 1) return 0; } for (int k = 0; k < q; k++) { int x; if (scanf("%d", &x) != 1) return 0; int lo = 1, hi = n; /* 아직 찾아볼 자리의 처음과 끝 */ int answer = 0; while (lo <= hi) { int mid = (lo + hi) / 2; /* int끼리 나누면 몫만 남는다 */ int book = books[mid - 1]; /* mid번째 자리는 배열의 mid - 1번 칸 */ printf("%d ", book); if (book == x) { answer = mid; break; } if (book < x) lo = mid + 1; else hi = mid - 1; } printf("%d\n", answer); } return 0;}
Craykonmain.cray · 32 lines
head = Console.ReadNumbers();n = head[0];books = Console.ReadNumbers();queries = Console.ReadNumbers();foreach (x in queries){ lo = 1; // 아직 찾아볼 자리의 처음과 끝 hi = n; seen = []; // 펼쳐 본 책 번호 answer = 0; while (lo <= hi) { mid = Mathf.Quot(lo + hi, 2); // 몫만 남긴다 book = books[mid - 1]; // mid번째 자리는 목록의 mid - 1번 칸 seen.Add(book); if (book == x) { answer = mid; break; } if (book < x) { lo = mid + 1; } else { hi = mid - 1; } } seen.Add(answer); Console.WriteLine(seen); // 목록은 빈칸으로 이어서 쓴다}