目录

二分查找算法

二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。

使用该算法的条件

必须是顺序排序,也就是已经排序好了的数据才可以用

示例代码

二分查找算法 - 图1

  1. int BinSearch(SeqList *R，int n,KeyType K)
  2. {
  3.     //在有序表R[0..n-1]中进行二分查找，成功时返回结点的位置，失败时返回-1
  4.     int low=0,high=n-1,mid；     //置当前查找区间上、下界的初值
  5.     while(low<=high)
  6.     {
  7.         //每次循环都先判断头和尾是否是找到该元素
  8.         // 重要
  9.         if(R[low].key==K)
  10.             return low;
  11.         // 重要
  12.         if(R[high].key==k)
  13.             return high;
  14.         //当前查找区间R[low..high]非空
  16.         mid=low+(high-low)/2;
  17.             /*使用(low+high)/2会有整数溢出的问题
  18.             （问题会出现在当low+high的结果大于表达式结果类型所能表示的最大值时，
  19.                 这样，产生溢出后再/2是不会产生正确结果的，而low+((high-low)/2)
  20.                 不存在这个问题*/
  21.         if(R[mid].key==K)
  22.           return mid;             //查找成功返回
  23.         if(R[mid].key<K)
  24.           low=mid+1;              //继续在R[mid+1..high]中查找
  25.         else
  26.           high=mid-1;             //继续在R[low..mid-1]中查找
  27.     }
  28.     if(low>high)
  29.         return -1;//当low>high时表示所查找区间内没有结果，查找失败
  30. }

%23%23%23%20%E7%9B%AE%E5%BD%95%0A%5Btoc%5D%0A%20%20%0A%0A%23%23%23%20%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE%E7%AE%97%E6%B3%95%0A%0A%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE%E4%B9%9F%E7%A7%B0%E6%8A%98%E5%8D%8A%E6%9F%A5%E6%89%BE%EF%BC%88Binary%20Search%EF%BC%89%EF%BC%8C%E5%AE%83%E6%98%AF%E4%B8%80%E7%A7%8D%E6%95%88%E7%8E%87%E8%BE%83%E9%AB%98%E7%9A%84%E6%9F%A5%E6%89%BE%E6%96%B9%E6%B3%95%E3%80%82%E4%BD%86%E6%98%AF%EF%BC%8C%E6%8A%98%E5%8D%8A%E6%9F%A5%E6%89%BE%E8%A6%81%E6%B1%82%E7%BA%BF%E6%80%A7%E8%A1%A8%E5%BF%85%E9%A1%BB%E9%87%87%E7%94%A8%E9%A1%BA%E5%BA%8F%E5%AD%98%E5%82%A8%E7%BB%93%E6%9E%84%EF%BC%8C%E8%80%8C%E4%B8%94%E8%A1%A8%E4%B8%AD%E5%85%83%E7%B4%A0%E6%8C%89%E5%85%B3%E9%94%AE%E5%AD%97%E6%9C%89%E5%BA%8F%E6%8E%92%E5%88%97%E3%80%82%0A%0A%23%23%23%20%E4%BD%BF%E7%94%A8%E8%AF%A5%E7%AE%97%E6%B3%95%E7%9A%84%E6%9D%A1%E4%BB%B6%0A%E5%BF%85%E9%A1%BB%E6%98%AF%E9%A1%BA%E5%BA%8F%E6%8E%92%E5%BA%8F%2C%E4%B9%9F%E5%B0%B1%E6%98%AF%E5%B7%B2%E7%BB%8F%E6%8E%92%E5%BA%8F%E5%A5%BD%E4%BA%86%E7%9A%84%E6%95%B0%E6%8D%AE%E6%89%8D%E5%8F%AF%E4%BB%A5%E7%94%A8%0A%0A%23%23%23%20%E7%A4%BA%E4%BE%8B%E4%BB%A3%E7%A0%81%0A!%5B6e84b75e24321e09a5268ac06939d03e.png%5D(evernotecid%3A%2F%2FD2915699-A379-4AAB-999E-4534E3EAFB1A%2Fappyinxiangcom%2F25807730%2FENResource%2Fp63)%0A%0A%60%60%60%0Aint%20BinSearch(SeqList%20R%EF%BC%8Cint%20n%2CKeyType%20K)%0A%7B%0A%20%20%20%20%2F%2F%E5%9C%A8%E6%9C%89%E5%BA%8F%E8%A1%A8R%5B0..n-1%5D%E4%B8%AD%E8%BF%9B%E8%A1%8C%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE%EF%BC%8C%E6%88%90%E5%8A%9F%E6%97%B6%E8%BF%94%E5%9B%9E%E7%BB%93%E7%82%B9%E7%9A%84%E4%BD%8D%E7%BD%AE%EF%BC%8C%E5%A4%B1%E8%B4%A5%E6%97%B6%E8%BF%94%E5%9B%9E-1%0A%20%20%20%20int%20low%3D0%2Chigh%3Dn-1%2Cmid%EF%BC%9B%20%20%20%20%20%2F%2F%E7%BD%AE%E5%BD%93%E5%89%8D%E6%9F%A5%E6%89%BE%E5%8C%BA%E9%97%B4%E4%B8%8A%E3%80%81%E4%B8%8B%E7%95%8C%E7%9A%84%E5%88%9D%E5%80%BC%0A%20%20%20%20while(low%3C%3Dhigh)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2F%E6%AF%8F%E6%AC%A1%E5%BE%AA%E7%8E%AF%E9%83%BD%E5%85%88%E5%88%A4%E6%96%AD%E5%A4%B4%E5%92%8C%E5%B0%BE%E6%98%AF%E5%90%A6%E6%98%AF%E6%89%BE%E5%88%B0%E8%AF%A5%E5%85%83%E7%B4%A0%0A%20%20%20%20%20%20%20%20%2F%2F%20%E9%87%8D%E8%A6%81%0A%20%20%20%20%20%20%20%20if(R%5Blow%5D.key%3D%3DK)%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20low%3B%0A%20%20%20%20%20%20%20%20%2F%2F%20%E9%87%8D%E8%A6%81%0A%20%20%20%20%20%20%20%20if(R%5Bhigh%5D.key%3D%3Dk)%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20high%3B%0A%20%20%20%20%20%20%20%20%2F%2F%E5%BD%93%E5%89%8D%E6%9F%A5%E6%89%BE%E5%8C%BA%E9%97%B4R%5Blow..high%5D%E9%9D%9E%E7%A9%BA%0A%20%20%20%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20mid%3Dlow%2B(high-low)%2F2%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%E4%BD%BF%E7%94%A8(low%2Bhigh)%2F2%E4%BC%9A%E6%9C%89%E6%95%B4%E6%95%B0%E6%BA%A2%E5%87%BA%E7%9A%84%E9%97%AE%E9%A2%98%0A%20%20%20%20%20%20%20%20%20%20%20%20%EF%BC%88%E9%97%AE%E9%A2%98%E4%BC%9A%E5%87%BA%E7%8E%B0%E5%9C%A8%E5%BD%93low%2Bhigh%E7%9A%84%E7%BB%93%E6%9E%9C%E5%A4%A7%E4%BA%8E%E8%A1%A8%E8%BE%BE%E5%BC%8F%E7%BB%93%E6%9E%9C%E7%B1%BB%E5%9E%8B%E6%89%80%E8%83%BD%E8%A1%A8%E7%A4%BA%E7%9A%84%E6%9C%80%E5%A4%A7%E5%80%BC%E6%97%B6%EF%BC%8C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%E8%BF%99%E6%A0%B7%EF%BC%8C%E4%BA%A7%E7%94%9F%E6%BA%A2%E5%87%BA%E5%90%8E%E5%86%8D%2F2%E6%98%AF%E4%B8%8D%E4%BC%9A%E4%BA%A7%E7%94%9F%E6%AD%A3%E7%A1%AE%E7%BB%93%E6%9E%9C%E7%9A%84%EF%BC%8C%E8%80%8Clow%2B((high-low)%2F2)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%E4%B8%8D%E5%AD%98%E5%9C%A8%E8%BF%99%E4%B8%AA%E9%97%AE%E9%A2%98%2F%0A%20%20%20%20%20%20%20%20if(R%5Bmid%5D.key%3D%3DK)%0A%20%20%20%20%20%20%20%20%20%20return%20mid%3B%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%E6%9F%A5%E6%89%BE%E6%88%90%E5%8A%9F%E8%BF%94%E5%9B%9E%0A%20%20%20%20%20%20%20%20if(R%5Bmid%5D.key%3CK)%0A%20%20%20%20%20%20%20%20%20%20low%3Dmid%2B1%3B%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%E7%BB%A7%E7%BB%AD%E5%9C%A8R%5Bmid%2B1..high%5D%E4%B8%AD%E6%9F%A5%E6%89%BE%0A%20%20%20%20%20%20%20%20else%0A%20%20%20%20%20%20%20%20%20%20high%3Dmid-1%3B%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%E7%BB%A7%E7%BB%AD%E5%9C%A8R%5Blow..mid-1%5D%E4%B8%AD%E6%9F%A5%E6%89%BE%0A%20%20%20%20%7D%0A%20%20%20%20if(low%3Ehigh)%0A%20%20%20%20%20%20%20%20return%20-1%3B%2F%2F%E5%BD%93low%3Ehigh%E6%97%B6%E8%A1%A8%E7%A4%BA%E6%89%80%E6%9F%A5%E6%89%BE%E5%8C%BA%E9%97%B4%E5%86%85%E6%B2%A1%E6%9C%89%E7%BB%93%E6%9E%9C%EF%BC%8C%E6%9F%A5%E6%89%BE%E5%A4%B1%E8%B4%A5%0A%7D%0A%0A%60%60%60