Skip to content

Instantly share code, notes, and snippets.

@RQN
Last active November 11, 2018 16:39
Show Gist options
  • Save RQN/a122880ee1a24d1a065592cdc33a437b to your computer and use it in GitHub Desktop.
Save RQN/a122880ee1a24d1a065592cdc33a437b to your computer and use it in GitHub Desktop.
二分探索がしたい
// using System;
// using System.Collections.Generic;
// using System.Linq;
public static class BinarySearch
{
/// <summary>
/// 指定された範囲の中央位置を取得します。小数点以下は切り上げます。
/// </summary>
private static int GetCenterIndex(int start, int last)
{
var center = (double)(last - ((last - start) / 2));
return (int)Math.Ceiling(center);
}
/// <summary>
/// 指定されたリストから、指定されたナンバーのデータを取得します。
/// </summary>
public static User Get(List<User> list, int number)
{
list = list.OrderBy(x => x.Number).ToList();
var start = 0;
var last = list.Count - 1;
if (list[start].Number == number) return list[start];
if (list[last].Number == number) return list[last];
if (list[start].Number > number ||
list[last].Number < number) return null;
while (true)
{
var center = GetCenterIndex(start, last);
if (list[center].Number == number) return list[center];
if ((last - start) == 1) return null;
if (list[center].Number < number) start = center;
else last = center;
}
}
}
// using System;
// using System.Collections.Generic;
class Program
{
static void Main(string[] args)
{
Console.Write("No. >> ");
var target = int.Parse(Console.ReadLine());
var list = GenerateList();
var user = BinarySearch.Get(list, target);
if (user != null)
Console.WriteLine($"[No.{user.Number}] {user.Name}: {user.Score} 点");
else
Console.WriteLine("指定されたデータは見つかりませんでした。");
Console.ReadKey();
}
/// <summary>
/// ソートされていないリストを生成します。
/// </summary>
static List<User> GenerateList() => new List<User>
{
new User{ Number = 29, Score = 600, Name = "工藤" },
new User{ Number = 11, Score = 700, Name = "田中" },
new User{ Number = 6, Score = 2700, Name = "中野" },
new User{ Number = 19, Score = 200, Name = "山下" },
new User{ Number = 31, Score = 800, Name = "小川" },
new User{ Number = 34, Score = 1000, Name = "三浦" },
new User{ Number = 23, Score = 500, Name = "佐藤" },
new User{ Number = 17, Score = 300, Name = "加藤" },
new User{ Number = 42, Score = 80, Name = "平沢" },
new User{ Number = 13, Score = 400, Name = "山田" }
};
}
public class User
{
public int Number { get; set; }
public int Score { get; set; }
public string Name { get; set; }
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment