{ }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); // 목록은 빈칸으로 이어서 쓴다}