算法导论之二分查找

系统管理员 2022-03-21 12:08 357阅读 0赞

二分查找的前提是要进行查找的序列必须是有序的，这里我们以升序为例。















1 2 3 4 5 6 7 8 9

start = 0, end = 8, mid = (0 + 8) / 2;

比如我们查找val = 2;

首先我们比较A[mid]和val, 如果val大，那么我们递归右边，否则我们递归左边。

  1. #include <iostream>
  2. using namespace std;
  4. int A[] = {1,2,3,4,5,6,7,9};
  5. int len = sizeof(A)/sizeof(A[0]);
  7. int Binary(int start, int end, int val)
  8. {
  9.     for (int j = start; j <= end; ++j) {
  10.         if (A[j] == val)
  11.             return j;
  12.     }
  13.     return -1;
  14. }
  16. int BinarySearch(int start, int end, int val)
  17. {
  18.     if (start == 0 && end == 0 && A[0] == val)//只有一位元素
  19.         return 0;
  20.     if (start < end) {
  21.         int mid = (start + end) / 2;
  22.         if (A[mid] > val) {//递归左边
  23.             BinarySearch(start, mid, val);
  24.             return Binary(start, mid, val);
  25.         }
  26.         else {//递归右边
  27.             BinarySearch(mid + 1, end, val);
  28.             return Binary(mid + 1, end, val);
  29.         }
  30.     }
  31.     return -1;
  32. }
  34. int main()
  35. {
  36.     cout << BinarySearch(0, len - 1, 10) << endl;
  37.     return 0;
  38. }

发表评论

表情：
评论列表 （有 0 条评论，357人围观）

还没有评论，来说两句吧...

相关阅读

    相关 简单算法 之 二分查找

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

    水深无声水深无声/ 0 赞/ 109 阅读

    相关 Java算法之二分查找

    一、二分查找又叫折半查找，查找要求是：待查找的 序列是有序的。 二、算法说明：每次取中间位置的值与带查找关键字比较，如果中间位置的值比待查找关键字大，则在前半部分循环这个查找

    迷南。迷南。/ 0 赞/ 64 阅读

    相关 算法之二分查找

    概念 二分查找针对的是一个有序的数据集合，查找思想有点类似分治思想，每次都通过跟区间的中间元素对比，将待查找的区间缩小为之前的一半，直到找到想要查找的元素，或是区间被缩小

    柔光的暖阳◎柔光的暖阳◎/ 0 赞/ 281 阅读

    相关 死磕算法之二分查找法

    二分查找又称折半算法，此算法作为一个经典的查找算法是我们不得不掌握的算法 这个算法查找的前提是查找的数据是有序的，我们以数组为例，使用二分查找法进行查找的时候我们应该先...

    红太狼红太狼/ 0 赞/ 528 阅读