本帖最后由 Mayi 于 2012-12-14 23:42 编辑
折半查找用与有序数组,是非常优秀的,其思想是比较查找值与数组中间元素,若相等,则结束查找,
若查找值大于中间值,则在数组后半部分查找(数组为升序),反之则在数组前半部分查找
其实现如下:- /// <summary>
- /// 折半查找
- /// </summary>
- /// <param name="arr">要查找的数组</param>
- /// <param name="keyValue">要查找的值</param>
- /// <returns>值在数组中的下标,若返回值为-1,则数组中没有此值</returns>
- /// 数组必须有序,且为升序
- static int BinarySearch(int[] arr, int keyValue)
- {
- int low = 0;
- int high = arr.Length - 1;
- int mid;
- while (low <= high)
- {
- mid = (low + high) / 2;
- if (keyValue == arr[mid])
- {
- return mid;
- }
- else if (keyValue < arr[mid])
- {
- high = mid - 1;
- }
- else
- {
- low = mid + 1;
- }
- }
- return -1;
- }
复制代码 和前两种算法(合并排序,快速排序)相比,(前两种都可以归结为分治法)折半查找是很不规范的分治法,也可以说是分治法的一种退化
其他算法请看这里
若有不对之处还请指出
|