競技プログラミングの鉄則をC#で解いてみた。A11 – Binary Search 1

問題

A11 – Binary Search 1 

考え方

問題文を理解する。

D日間開催されるイベントにN人の客がそれぞれ連続した特定の期間訪れる。
それぞれの日にちでは何人客が訪れたかを答えろ。

解く

2分探索通りに書けばOK。
二分探索についてはこちらの本を参考にした。


提出したコード

using System;
using System.Linq;
using System.Collections.Generic;
class Program
{
    static void Main(string[] args)
    {
        int[] nx = Console.ReadLine().Split(' ').Select(i => int.Parse(i)).ToArray();
        int n = nx[0];
        int x = nx[1];
        int[] a = Console.ReadLine().Split(' ').Select(i => int.Parse(i)).ToArray();
        int result = BinarySearch(a, x);
        Console.WriteLine(result + 1);
    }

    private static int BinarySearch(int[] e, int key)
    {
        int left = 0;
        int right = e.Length - 1;

        int harf = (left + right) / 2;

        while(left <= right)
        {
            harf = left + (right - left) / 2;
            if (e[harf] == key) return harf;
            else if (e[harf] < key)
            {
                left = harf + 1; //{0,1}ならindexは常に0になり、永遠にharf=0でループしてしまうから+1している。
            }else if (e[harf] > key)
            {
                right = harf - 1;
            }
        }

        return -1;
    }
}

Atcoder

Posted by admin