이분 탐색

def lower_bound(a, x):    lo, hi = 0, len(a)  # 답은 lo부터 hi까지 가운데 어딘가    while lo < hi:        mid = (lo + hi) // 2        if a[mid] < x:            lo = mid + 1  # mid와 그 왼쪽은 모두 x보다 작아요        else:            hi = mid  # mid와 그 오른쪽은 모두 x 이상이에요    return lo  # x 이상인 첫 자리(없으면 len(a))  n, q = map(int, input().split())scores = list(map(int, input().split()))for x in map(int, input().split()):    pos = lower_bound(scores, x)  # x보다 낮은 점수의 개수이기도 해요    found = pos < n and scores[pos] == x    print(pos, "yes" if found else "no")

function lowerBound(a, x) {  let lo = 0, hi = a.length; // 답은 lo부터 hi까지 가운데 어딘가  while (lo < hi) {    const mid = Math.floor((lo + hi) / 2);    if (a[mid] < x) lo = mid + 1; // mid와 그 왼쪽은 모두 x보다 작아요    else hi = mid; // mid와 그 오른쪽은 모두 x 이상이에요  }  return lo; // x 이상인 첫 자리(없으면 a.length)} const lines = require("fs").readFileSync(0, "utf8").split("\n");const [n] = lines[0].split(" ").map(Number);const scores = lines[1].trim().split(" ").map(Number);for (const x of lines[2].trim().split(" ").map(Number)) {  const pos = lowerBound(scores, x); // x보다 낮은 점수의 개수이기도 해요  const found = pos < n && scores[pos] === x;  console.log(pos, found ? "yes" : "no");}

import { readFileSync } from "node:fs"; function lowerBound(a: number[], x: number): number {  let lo = 0, hi = a.length; // 답은 lo부터 hi까지 가운데 어딘가  while (lo < hi) {    const mid: number = Math.floor((lo + hi) / 2);    if (a[mid] < x) lo = mid + 1; // mid와 그 왼쪽은 모두 x보다 작아요    else hi = mid; // mid와 그 오른쪽은 모두 x 이상이에요  }  return lo; // x 이상인 첫 자리(없으면 a.length)} const lines: string[] = readFileSync(0, "utf8").split("\n");const [n] = lines[0].split(" ").map(Number);const scores: number[] = lines[1].trim().split(" ").map(Number);for (const x of lines[2].trim().split(" ").map(Number)) {  const pos: number = lowerBound(scores, x); // x보다 낮은 점수의 개수이기도 해요  const found: boolean = pos < n && scores[pos] === x;  console.log(pos, found ? "yes" : "no");}

import java.util.Scanner; public class Main {    static int lowerBound(int[] a, int x) {        int lo = 0, hi = a.length; // 답은 lo부터 hi까지 가운데 어딘가        while (lo < hi) {            int mid = lo + (hi - lo) / 2; // (lo + hi) / 2는 큰 수에서 넘쳐요            if (a[mid] < x) lo = mid + 1; // mid와 그 왼쪽은 모두 x보다 작아요            else hi = mid; // mid와 그 오른쪽은 모두 x 이상이에요        }        return lo; // x 이상인 첫 자리(없으면 a.length)    }     public static void main(String[] args) {        Scanner sc = new Scanner(System.in);        int n = sc.nextInt(), q = sc.nextInt();        int[] scores = new int[n];        for (int i = 0; i < n; i++) scores[i] = sc.nextInt();        for (int i = 0; i < q; i++) {            int x = sc.nextInt();            int pos = lowerBound(scores, x); // x보다 낮은 점수의 개수이기도 해요            boolean found = pos < n && scores[pos] == x;            System.out.println(pos + " " + (found ? "yes" : "no"));        }    }}

using System; class Program{    static int LowerBound(int[] a, int x)    {        int lo = 0, hi = a.Length; // 답은 lo부터 hi까지 가운데 어딘가        while (lo < hi)        {            int mid = lo + (hi - lo) / 2; // (lo + hi) / 2는 큰 수에서 넘쳐요            if (a[mid] < x) lo = mid + 1; // mid와 그 왼쪽은 모두 x보다 작아요            else hi = mid; // mid와 그 오른쪽은 모두 x 이상이에요        }        return lo; // x 이상인 첫 자리(없으면 a.Length)    }     static void Main()    {        int n = int.Parse(Console.ReadLine().Split(' ')[0]);        int[] scores = Array.ConvertAll(Console.ReadLine().Trim().Split(' '), int.Parse);        foreach (string s in Console.ReadLine().Trim().Split(' '))        {            int x = int.Parse(s);            int pos = LowerBound(scores, x); // x보다 낮은 점수의 개수이기도 해요            bool found = pos < n && scores[pos] == x;            Console.WriteLine(pos + " " + (found ? "yes" : "no"));        }    }}

#include <iostream>#include <vector> int lowerBound(const std::vector<int> &a, int x) {    int lo = 0, hi = a.size(); // 답은 lo부터 hi까지 가운데 어딘가    while (lo < hi) {        int mid = lo + (hi - lo) / 2; // (lo + hi) / 2는 큰 수에서 넘쳐요        if (a[mid] < x) lo = mid + 1; // mid와 그 왼쪽은 모두 x보다 작아요        else hi = mid; // mid와 그 오른쪽은 모두 x 이상이에요    }    return lo; // x 이상인 첫 자리(없으면 a.size())} int main() {    int n, q;    std::cin >> n >> q;    std::vector<int> scores(n);    for (int &s : scores) std::cin >> s;    for (int i = 0; i < q; i++) {        int x;        std::cin >> x;        int pos = lowerBound(scores, x); // x보다 낮은 점수의 개수이기도 해요        bool found = pos < n && scores[pos] == x;        std::cout << pos << ' ' << (found ? "yes" : "no") << '\n';    }}

#include <stdio.h> int lower_bound(const int *a, int n, int x) {    int lo = 0, hi = n; // 답은 lo부터 hi까지 가운데 어딘가    while (lo < hi) {        int mid = lo + (hi - lo) / 2; // (lo + hi) / 2는 큰 수에서 넘쳐요        if (a[mid] < x) lo = mid + 1; // mid와 그 왼쪽은 모두 x보다 작아요        else hi = mid; // mid와 그 오른쪽은 모두 x 이상이에요    }    return lo; // x 이상인 첫 자리(없으면 n)} int main(void) {    int n, q;    static int scores[10000];    scanf("%d %d", &n, &q);    for (int i = 0; i < n; i++) scanf("%d", &scores[i]);    for (int i = 0; i < q; i++) {        int x;        scanf("%d", &x);        int pos = lower_bound(scores, n, x); // x보다 낮은 점수의 개수이기도 해요        int found = pos < n && scores[pos] == x;        printf("%d %s\n", pos, found ? "yes" : "no");    }    return 0;}

lowerBound(a, x){    lo = 0; // 답은 lo부터 hi까지 가운데 어딘가    hi = a.개수;    동안 (lo < hi)    {        mid = 수학.몫(lo + hi, 2);        만약 (a[mid] < x)        {            lo = mid + 1; // mid와 그 왼쪽은 모두 x보다 작아요        }        아니면        {            hi = mid; // mid와 그 오른쪽은 모두 x 이상이에요        }    }    돌려주기 lo; // x 이상인 첫 자리(없으면 a.개수)} first = 콘솔.수들읽기();n = first[0];scores = 콘솔.수들읽기();각각 (x 에서 콘솔.수들읽기()){    pos = lowerBound(scores, x); // x보다 낮은 점수의 개수이기도 해요    found = pos < n && scores[pos] == x;    콘솔.쓰기(pos + " " + (found ? "yes" : "no"));}