二分查找的基本思想是在一个有序序列中,每次取待查找序列的中间元素跟目标元素进行比较,如果小于,则待查找序列定位到后半段,反之则定位到前半段,这样每次比较后都可以将范围缩小到原来的1/2. 注意:二分查找的前提是待查找序列必须是有序的.
下面给出的是C代码的递归与非递归形式: ------------------------------------------------
int b_recursion(int left,int right,int *data,int key) { int mid=0; ///左右边界可以取到相等(待查找序列内只有一个元素), //但是右边界小于左边界表示数据不在目标队列内,查找结实 if(right < left) return -1;
mid=(left+right)/2;
if(data[mid]==key) return mid; else if(key < data[mid])//使用左段 return b_recursion(left,mid-1,data,key); else//使用右段 return b_recursion(mid+1,right,data,key);
}
//非递归实现 // int *data 表示数组 int b_search(int left,int right, int *data,int key) { int mid=0;
while(left <=right) { mid=(left+right)/2;
if( data[mid]==key) return mid; else if(key > data[mid]) left=mid+1; else if(key < data[mid]) right=mid-1; } return -1; } ------------------------------------- 查找跟排序在一般Web编程中多少是会用到的,不过在.net2.0中你并不需要自己编写代码来实现,.net2.0的System.Collections.Generic命名空间下的List 类可以满足一般的自定义类的排序与查找任务,你也可以直接使用Array类的静太方法 public static void Sort (T[] array, IComparer comparer); 进行排序,使用 public static int BinarySearch (T[] array, T value, IComparer comparer);进行查找. 下面是MS实现的二分查找代码: ________________________________________
public virtual int BinarySearch(T[] array, int index, int length, T value, IComparer comparer) { if (comparer == null) { comparer = Comparer .Default; } //MS里好象num1,num2..numx 用的比较多 int num = index; int num2 = (index + length) - 1; while (num <= num2) { int num4; int num3 = num + ((num2 - num) >> 1); //使用移位进行除二操作 try { num4 = comparer.Compare(array[num3], value); } catch (Exception exception) { throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_IComparerFailed"), exception); } if (num4 == 0) { return num3; } if (num4 < 0) { num = num3 + 1; } else { num2 = num3 - 1; } } return ~num; }
