数据结构算法（一）之二分查找

internal class Program
    {
        static void Main(string[] args)
        {
            var n = 50;
            var random = new Random();
            while (n-- > 0)
                RandomTest(random);
			Console.ReadLine();
        }

		static int SortedIndexOf(int[] nums, int value)
		{
			if (nums == null || value < nums[0] || value > nums[nums.Length - 1])
				return -1;
			return SortedIndexOfImpl(nums, 0, nums.Length, value);
		}

		static int SortedIndexOfImpl(int[] nums, int offset, int length, int value)
		{
			if (length == 0)
				return -1;
			if (nums[offset] == value)
				return offset;
			if (length == 1)
				return -1;
			int half = length / 2;
			int mid = offset + half;
			if (nums[mid] > value)
				return SortedIndexOfImpl(nums, offset, half, value);
			else if (nums[mid] == value)
				return SortedIndexOfImpl(nums, offset + 1, half, value);
			else
				return SortedIndexOfImpl(nums, mid + 1, length - half - 1, value);
		}

		static void RandomTest(Random random)
		{
			var length = random.Next(1, 50);
			var maxValue = length / 2 + 1;

			var target = random.Next(maxValue); //最大值区间
			var list = new List<int>(length);
			while (length-- > 0)
				list.Add(random.Next(maxValue));
			list.Sort();

			var groundTruth = list.IndexOf(target);

			//var actualResult = SortedIndexOf(list.ToArray(), target);

			Console.WriteLine("SortedIndexOf([{0}], {1})", string.Join(",", list), target);
			Console.WriteLine("Expected: {0}", groundTruth);
			//Console.WriteLine("Actual: {0}", actualResult);
            Console.WriteLine("+++++++++++++++++++++++++++++++++");

			//if (groundTruth != actualResult)
			//{
			//	throw new Exception("Assertion Failed");
			//}
		}

		//public static void Main()
		//{
		//	var n = 50;
		//	var random = new Random();
		//	while (n-- > 0)
		//		RandomTest(random);
		//}
	}