{ }codelper
二分探索P0375

司書が取り出してみた本

本棚に本 n 冊が本の番号の小さい順に並んでいる。
本の番号はすべて異なり、位置は左から 1 番、2 番、…、n 番である。
司書は本の番号 x を探すとき、次のようにする。
はじめは、探す位置の最初が 1 番、最後が n 番である。
最初の位置の番号と最後の位置の番号を足して 2 で割った商（余りは捨てる）が指す位置の本を取り出してみる。
その本の番号が x なら探すのを終える。
その本の番号が x より小さければ最初をその位置のすぐ次に移し、x より大きければ最後をその位置のすぐ前に移す。
移した後に最初が最後より大きくなっていたら、その本はないので探すのを終える。
そうでなければ、新しい最初と最後で同じ方法を繰り返し、次の本を取り出してみる。
一行目に n と q が、二行目に本の番号 n 個が、三行目に探す番号 q 個が、空白一つで区切って与えられる。
探す番号ごとに一行に、司書が取り出してみた本の番号を取り出した順に書き、最後に見つけた位置の番号を書いて、空白一つで区切って出力せよ。
見つからなければ位置の番号の代わりに 0 を書く。
例の本棚で x = 15 なら、最初に取り出した本が 15 なので "15 3" を出力する。

入力
1 ≤ n ≤ 100、1 ≤ q ≤ 100、1 ≤ 本の番号 ≤ 1,000、1 ≤ x ≤ 1,000（すべて整数、本の番号は昇順で互いに異なる）
出力
探す番号ごとに一行：取り出してみた本の番号と、見つけた位置の番号（なければ 0）
例 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
入力(stdin)

実行すると、これらの行が順に input()・標準入力に渡されます(実行中に入力を求めません)。

$ 準備完了

コードを入力して解くにはパソコンで開いてください。モバイルでは問題と解答を見られます。

ほかの言語では？言語別の解答を見る · 8 言語の解答

真ん中の位置を求めるとき、商だけを残す方法は言語ごとに違います。
Python (lo + hi) // 2、C・C++・Java・C# は int どうしの (lo + hi) / 2、JS・TS Math.floor((lo + hi) / 2)、Craykon 数学.商(lo + hi, 2)。
探してくれる道具もあります。
Python bisect.bisect_left、C++ std::lower_bound、Java Arrays.binarySearch、C# Array.BinarySearch は、例の 42 に対して 0 から数えた位置 4 だけを教えてくれます。
どの本を取り出したかは教えてくれないので、この問題では自分で書きます。
落とし穴その一：繰り返しの条件は lo <= hi です。
lo < hi と書くと、残りの位置が一つのときにその本を取り出さないので、例の四行目が 15 42 0 になります。
落とし穴その二：JS で Math.floor なしに / で割ると真ん中が 3.5 になり、その位置の本は undefined なので、例のすべての行が空白二つの後ろに 0 だけになります。
Craykon で / を使うと、[ ] の中には整数の番号を書くようにというエラーで止まります。
落とし穴その三：Python で本の番号を int で数に変えないと文字列として比べるので、"15" < "8" が真になります。
例の二行目が 15 42 77 0 になります。
落とし穴その四：真ん中を (lo + hi + 1) / 2 と切り上げると、違う本を取り出します。
例の一行目が 20 77 42 5 になります。
落とし穴その五：位置を 0 から数えてその番号をそのまま出力すると、位置が一つずつ小さくなります。
例の一行目が 15 42 4 になり、最後の行は 15 3 0 なので、見つけたのに見つからなかったように見えます。

Pythonmain.py · 19 行
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 行
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 行
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 行
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 行
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 行
#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 行
#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 行
head = コンソール.数読み();n = head[0];books = コンソール.数読み();queries = コンソール.数読み();それぞれ (x の中 queries){    lo = 1; // 아직 찾아볼 자리의 처음과 끝    hi = n;    seen = []; // 펼쳐 본 책 번호    answer = 0;    間 (lo <= hi)    {        mid = 数学.商(lo + hi, 2); // 몫만 남긴다        book = books[mid - 1]; // mid번째 자리는 목록의 mid - 1번 칸        seen.追加(book);        もし (book == x)        {            answer = mid;            抜ける;        }        もし (book < x)        {            lo = mid + 1;        }        でなければ        {            hi = mid - 1;        }    }    seen.追加(answer);    コンソール.書く(seen); // 목록은 빈칸으로 이어서 쓴다}