binsearcharray.cs

网上流传的5个面试题目

using System;

namespace BinSearch
{
	/// <summary>
	/// BinSearchArray 二分法查找的类。
	/// </summary>
	public class BinSearchArray
	{
		public BinSearchArray()
		{
			Random rd = new Random();
			intArray = new int[50];
			for (int i = 0; i < 50; ++i)
				intArray[i] = rd.Next(1, 200);
		}

		private int[] intArray;

		/// <summary>
		/// 输出数据内容。
		/// </summary>
		public void OutPutContent()
		{
			for (int i = 0; i < 50; ++i)
			{
				Console.WriteLine("{0}\t{1}", i, intArray[i]);
			}
		}

		/// <summary>
		/// 从小到大排序。这里使用是的选择排序法。
		/// </summary>
		public void Sort()
		{
			for (int i = 0; i < 50; ++i)
				for (int j = i; j < 50; ++j)
					if (intArray[i] > intArray[j])
					{
						int temp = intArray[i];
						intArray[i] = intArray[j];
						intArray[j] = temp;
					}
		}
		/// <summary>
		/// 二分法查找。
		/// </summary>
		/// <param name="n">要被查找的键值。</param>
		/// <returns>若存在返回值则返回位置，否则返回-1。</returns>
		public int BinSearch(int n)
		{
			return BinSearch(n, 0, 49);
		}

		/// <summary>
		/// 真正的二分法查找实现。我比较喜欢使用递归。
		/// </summary>
		/// <param name="n">要被查找的键值。</param>
		/// <param name="begin">被查找的起始位置</param>
		/// <param name="end"></param>
		/// <returns>若存在返回值则返回位置，否则返回-1。</returns>
		private int BinSearch(int n, int begin, int end)
		{
			if (begin > end)
				return -1;
			int pos = (begin + end) / 2;
			if (intArray[pos] < n)
				return BinSearch(n, pos + 1, end);
			if (intArray[pos] > n)
				return BinSearch(n, begin, pos - 1);
			return pos;
		}
	}
}