6.2.2 折半查找.md

↩返回主页

⬅上一节 / 下一节➡

---

6.2.2 折半查找

  折半查找 又称二分查找，仅适用于有序的顺序表。

• 算法思想

  • 首先将给定值 key 与表中中间位置元素的关键字比较

  • 若相等，则返回该元素的位置

  • 若不等，则在前半部分或者是后半部分进行查找

    • 若 key 小于中间元素，则查找前半部分

    • 若 key 大于中间元素，则查找后半部分

  • 重复该过程，直到找到查找的元素为止；或者查找失败

• C 语言实现：

  int Binary_Search(SeqList L, ElemType key) {
      int low=0, high=L.TableLen-1, mid;
      while(low <= high) {
          mid = (low+high)/2;
          if(L.elem[mid] == key)
              return mid;
          else if(L.elem[mid] > key)
              high = mid-1;
          else
              low = mid+1;
      }
      return -1;
  }

• 折半查找判定树

  

• 平均查找长度 ASL

  • 成功：log₂(n+1)-1

  • 即时间复杂度为 O(log₂n)

💡 题型

  xxx

单项选择题

1. xxxx（ ）

   A. xxx
   B. XX
   C. Xx
   D. xX
   
   

   查看解析

   答案：x

---

返回顶部⤴

-- 完 --