競技プログラミングの鉄則をC#で解いてみた。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;
}
}
ディスカッション
コメント一覧
まだ、コメントがありません