分类目录

链接

2011 年 12 月
一 二 三 四 五 六 日
 1234
567891011
12131415161718
19202122232425
262728293031  

近期文章

热门标签

新人福利，免费薅羊毛

现在位置:    首页 ＞ .NET ＞ 正文
搜索算法
 2011-12-02 21:47 .NET 暂无评论 阅读(1,710)
  1. 1. Searching for Minimum and Maximum Values
  2.  
  3. //这个太简单，不多说，直接贴代码。
  4. static int FindMin(int[] array)
  5. {
  6.     var min = array[0];
  7.     foreach (var i in array)
  8.     {
  9.         if (i < min) min = i;
  10.     }
  11.  
  12.     return min;
  13. }
  14.  
  15. static int FindMax(int[] array)
  16. {
  17.     var max = array[0];
  18.     foreach (var i in array)
  19.     {
  20.         if (i > max) max = i;
  21.     }
  22.  
  23.     return max;
  24. }
  25.  
  26. static void Main(string[] args)
  27. {
  28.     var array = new[] { 3, 7, 6, 5, 8, 4, 9, 2, 0, 1 };
  29.     Console.WriteLine(FindMin(array));
  30.     Console.WriteLine(FindMax(array));
  31. }
  32.  
  33. 2. Binary Search
  34.  
  35. //这个搜索算法比较常用，不过它有个前提条件就是集合必须是排序过的。将集合不断切割成左右两份，通过判断中间值来缩小搜索范围。
  36.  
  37. //举例来说：
  38.  
  39. 0,1,2,3,4,5,6,7,8,9 -> 要搜索 8 的索引位置。
  40.  
  41. 第一次: [0,1,2,3] [4] [5,6,7,8,9] ------ 8 > 4，范围缩小到右端。
  42. 第二次: [5,6] [7] [8,9] ------ 8 > 7，范围缩小到右端。
  43. 第三次: [8] [9]，完成搜索。
  44. static int BinarySearch(int[] array, int value)
  45. {
  46.     var lower = 0;
  47.     var upper = array.Length - 1;
  48.     
  49.     while (lower <= upper)
  50.     {
  51.         var middle = (lower + upper) / 2;
  52.  
  53.         if (array[middle] == value)
  54.             return middle;
  55.         else if (array[middle] < value)
  56.             lower = middle + 1;
  57.         else
  58.             upper = middle - 1;
  59.  
  60.     }
  61.  
  62.     return -1;
  63. }
  64.  
  65. static void Main(string[] args)
  66. {
  67.     var array = new[] { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
  68.     Console.WriteLine(BinarySearch(array, 8));
  69. }
  70.  
  71. 当然，我们可以用递归来替代循环。
  72. static int BinarySearch(int[] array, int lower, int upper, int value)
  73. {
  74.     if (lower > upper) return -1;
  75.  
  76.     var middle = (lower + upper) / 2;
  77.  
  78.     if (array[middle] == value)
  79.         return middle;
  80.     else if (array[middle] < value)
  81.         return BinarySearch(array, middle + 1, upper, value);
  82.     else
  83.         return BinarySearch(array, lower, middle - 1, value);
  84. }
  85.  
  86. static void Main(string[] args)
  87. {
  88.     var array = new[] { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
  89.     Console.WriteLine(BinarySearch(array, 0, array.Length - 1, 8));
  90. }

============ 欢迎各位老板打赏~ ===========

关键字:
【上篇】
【下篇】

与本文相关的文章

该日志由 Bruce 于2011年12月02日发表在.NET分类下

本文版权归Bruce's Blog所有，转载引用请完整注明以下信息：
本文作者：Bruce
本文地址：搜索算法 | Bruce's Blog

发表评论

留言无头像?