A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

© 马毅 中级黑马   /  2012-12-14 23:38  /  1879 人查看  /  1 人回复  /   0 人收藏 转载请遵从CC协议 禁止商业使用本文

本帖最后由 Mayi 于 2012-12-14 23:42 编辑

折半查找用与有序数组,是非常优秀的,其思想是比较查找值与数组中间元素,若相等,则结束查找,
若查找值大于中间值,则在数组后半部分查找(数组为升序),反之则在数组前半部分查找

其实现如下:
  1.         /// <summary>
  2.         /// 折半查找
  3.         /// </summary>
  4.         /// <param name="arr">要查找的数组</param>
  5.         /// <param name="keyValue">要查找的值</param>
  6.         /// <returns>值在数组中的下标,若返回值为-1,则数组中没有此值</returns>
  7.         /// 数组必须有序,且为升序
  8.         static int BinarySearch(int[] arr, int keyValue)
  9.         {
  10.             int low = 0;
  11.             int high = arr.Length - 1;
  12.             int mid;
  13.             while (low <= high)
  14.             {
  15.                 mid = (low + high) / 2;
  16.                 if (keyValue == arr[mid])
  17.                 {
  18.                     return mid;
  19.                 }
  20.                 else if (keyValue < arr[mid])
  21.                 {
  22.                     high = mid - 1;
  23.                 }
  24.                 else
  25.                 {
  26.                     low = mid + 1;
  27.                 }
  28.             }
  29.             return -1;
  30.         }
复制代码
和前两种算法(合并排序,快速排序)相比,(前两种都可以归结为分治法)折半查找是很不规范的分治法,也可以说是分治法的一种退化
其他算法请看这里
若有不对之处还请指出

评分

参与人数 1技术分 +1 收起 理由
宋天琪 + 1

查看全部评分

1 个回复

倒序浏览
值得学习ing!
回复 使用道具 举报
您需要登录后才可以回帖 登录 | 加入黑马