二分查找

　 二分查找的基本思想是在一個有序序列中,每次取待查找序列的中間元素跟目標元素進行比較,如果小於,則待查找序列定位到後半段,反之則定位到前半段,這樣每次比較後都可以將范圍縮小到原來的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<T>類可以滿足一般的自定義類的排序與查找任務,你也可以直接使用Array類的靜太方法public static void Sort<T>(T[] array, IComparer<T> comparer);進行排序,使用public static int BinarySearch<T>(T[] array, T value, IComparer<T> comparer);進行查找.

下面是MS實現的二分查找代碼:
________________________________________

public virtual int BinarySearch(T[] array, int index, int length, T value, IComparer<T> comparer)
{
    if (comparer == null)
    {
        comparer = Comparer<T>.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;
}