折半查找

折半查找（Binary Search）技术，又称为二分查找，其前提是线性表中的记录有序，线性表必须采用线性存储。

折半查找的思想

• 取中间数字作为比较对象，若给定值与中间记录的关键字相等，则查找成功；
• 若给定值小于中间数字，则在左半区进行查找；
• 若给定值大于中间记录的关键字，则在右半区进行查找
• 不断重复上述步骤，直到找到——查找成功或查找区域无记录——查找失败

  算法实现

  int Binary_Search(int *a,int n, int key){
      int low ,high,mid;
      low =l;
      high = n;
      while(lwo<=high){< span>        mid = (low+high) /2;        if(key            high=mid-1；        else if (key>a[mid])            low=mid+1;        else             return mid;    }    return 0;}
          mid = (low+high) /2;
          if(key            high=mid-1；        else if (key>a[mid])            low=mid+1;        else             return mid;    }    return 0;}
              high=mid-1；
          else if (key>a[mid])
              low=mid+1;
          else 
              return mid;
      }
  
      return 0;
  }

算法分析

• 将这个有序数组转化为二叉树，也就是说折半查找把一棵树分为两棵子树
• 只需要查找其中一个子树，等同于工作量少了一半，再继续拆分成两个子树，工作量少了一半
• 最好的情况一定是1次直接查找到，最坏是查找[log2^n]+1次

算法复杂度