二分法：二分查找（递归+非递归）实现

首页 > 二分法：二分查找（递归+非递归）实现

二分法：二分查找（递归+非递归）实现

二分查找又称折半查找，首先，假设表中元素是按升序排列，将表中间位置的关键字与查找关键字比较:

如果两者相等，则查找成功;
否则利用中间位置将表分成前、后两个子表:

1)如果中间位置的关键字大于查找关键字，则进一步查找前一子表

2)否则进一步查找后一子表重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。

例如：target = 200

arr = [-1,2,5,20,90,100,320]

使用二分查找，从arr中查找target是否存在

取中间位置为20 ，20 < 200
缩小查找空间 [90,100,320]，二分查找中间位置100 < 200
缩小查找空间[320,320],begin == end
未找到 200，返回失败

问题描述如下：

已知一个排序数组A，如 A = [-1, 2, 5, 20, 90, 100, 207, 800]，另外一个乱序数组B，如 B = [50, 90, 3, -1, 207, 80]，求B中的任意某个元素，是否在A中出现，结果存储在数组C中，出现用1代表，未出现用0代表，如，C = [0, 1, 0, 1, 1, 0]。

以上过程如果使用暴力搜索，则需要O(n*m)即O(n^2);

这里使用二分查找则仅仅需要O(log2n)的时间复杂度:

n/2 + n/4 + … + n/2^k (k为循环的次数)

由于你n/2^k （取最坏的情况，最后一次仅剩下一个数）

即令n/2^k=1

可得k=log2n,（是以2为底，n的对数）

所以时间复杂度可以表示O(h)=O(log2n)

递归实现如下:

bool find_part(std::vector<int> arr, int begin, int end, int target) { if (begin > end) { //结束条件return false;}int mid = (begin + end) / 2;if (arr[mid] == target) { return true;} else if (arr[mid] > target) { return find_part(arr, begin, mid -1, target);} else { return find_part(arr, mid + 1, end, target);}
}std::vector<int> get_result(std::vector<int> arr, std::vector<int> target) { std::vector<int> v;for (int i = 0;i < target.size(); ++i) { int result = find_part(arr,0,arr.size() - 1, target[i]);v.push_back(result);}return v;
}

非递归实现：

std::vector<int> find_part_norecur(std::vector<int> arr1, std::vector<int> target) { std::vector<int> result;for (int i = 0;i < target.size(); ++i) { int begin = 0;int end = arr1.size();while(begin <= end) { int mid = (begin +  end) / 2;if(arr1[mid] == target[i]) { result.push_back(1);break;} else if (arr1[mid] > target[i]) { end = mid - 1;} else { begin = mid + 1;}}if (begin >= end){ result.push_back(0);}}return result;
}

测试代码如下:

#include 
#include using namespace std;bool find_part(std::vector<int> arr, int begin, int end, int target) { if (begin > end) { return false;}int mid = (begin + end) / 2;if (arr[mid] == target) { return true;} else if (arr[mid] > target) { return find_part(arr, begin, mid -1, target);} else { return find_part(arr, mid + 1, end, target);}
}std::vector<int> get_result(std::vector<int> arr, std::vector<int> target) { std::vector<int> v;for (int i = 0;i < target.size(); ++i) { int result = find_part(arr,0,arr.size() - 1, target[i]);v.push_back(result);}return v;
}std::vector<int> find_part_norecur(std::vector<int> arr1, std::vector<int> target) { std::vector<int> result;for (int i = 0;i < target.size(); ++i) { int begin = 0;int end = arr1.size();while(begin <= end) { int mid = (begin +  end) / 2;if(arr1[mid] == target[i]) { result.push_back(1);break;} else if (arr1[mid] > target[i]) { end = mid - 1;} else { begin = mid + 1;}}if (begin >= end){ result.push_back(0);}}return result;
}int main(int argc, char const *argv[])
{ std::vector<int> arr1;std::vector<int> target;int n;cin >> n;for (int i = 0;i < n; ++i) { int tmp;cin >> tmp;arr1.push_back(tmp);}int t;cin >> t;for (int i = 0;i < t; ++i) { int tmp;cin >> tmp;target.push_back(tmp);}	std::vector<int> result;// result = get_result(arr1, target);result = find_part_norecur(arr1,target);for (int i = 0;i < result.size(); ++i) { cout << result[i] << " ";}return 0;
}

输出如下:

#输入序列数组
5   
2 3 4 5 6
#输入目标数组
3
1 3 5
#输出
0 1 1

更多相关：

java 读取excel_Java12POI操作Excel

Apache POI是一个开源的利用Java读写Excel，WORD等微软OLE2组件文档的项目。我的需求是对Excel的数据进行导入或将数据以Excel的形式导出。先上简单的测试代码：package com.xing.studyTest.poi;import java.io.FileInputSt...
C++ 生成随机数

要取得[a,b)的随机整数，使用(rand() % (b-a))+ a; 要取得[a,b]的随机整数，使用(rand() % (b-a+1))+ a; 要取得(a,b]的随机整数，使用(rand() % (b-a))+ a + 1; 通用公式:a + rand() % n；其中的a是起始值，n是整数的范围。要取得a到b之间的...
基于C++的本征图像分解(Intrinsic Image Decomposition)

利用本征图像分解(Intrinsic Image Decomposition)算法，将图像分解为shading(illumination) image 和 reflectance(albedo) image，计算图像的reflectance image。 Reflectance Image 是指在变化的光照条件下能够维持不变的图像部分...
剑指offer：面试题39. 数组中出现次数超过一半的数字

题目：面试题39. 数组中出现次数超过一半的数字数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。你可以假设数组是非空的，并且给定的数组总是存在多数元素。示例 1: 输入: [1, 2, 3, 2, 2, 2, 5, 4, 2] 输出: 2 限制： 1 <= 数组长度 <= 50000 解题： cl...
剑指offer：面试题33. 二叉搜索树的后序遍历序列

题目：二叉搜索树的后序遍历序列输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。参考以下这颗二叉搜索树： 5 / 2 6 / 1 3示例 1：输入: [1,6,3,2,5] 输出...
剑指offer：面试题04. 二维数组中的查找

题目：二维数组中的查找在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。示例: 现有矩阵 matrix 如下： [[1, 4, 7, 11, 15],[2, 5, 8, 12, 1...
valgrind 使用 kcachegrind 查看函数运行时间

安装首先安装运行分析函数时间的工具 kcachegrind 下载安装包 http://kcachegrind.sourceforge.net/，下载最新的 tar.gz 文件解压文件，进入解压之后的目录，从 README 中可以找到安装方式，这里记录一下 cmake . make -j8 sudo make install...
Linux ISCSI配置

一、简介 iSCSI（internet SCSI）技术由IBM公司研究开发，是一个供硬件设备使用的、可以在IP协议的上层运行的SCSI指令集，这种指令集合可以实现在IP网络上运行SCSI协议，使其能够在诸如高速千兆以太网上进行路由选择。iSCSI技术是一种新储存技术，该技术是将现有SCSI接口与以太网络(Ethernet)技术结合，使...
记录CSS3 target伪类简介

CSS3 target伪类是众多实用的CSS3特性中的一个。它用来匹配文档(页面)的URI中某个标志符的目标元素。具体来说，URI中的标志符通常会包含一个”#”字符，然后后面带有一个标志符名称，比如#respond，target就是用来匹配ID为respond的元素的。现在在页面中，点击一个ID链接后，页面只会跳转到相应的位置，但...
flash玩转cookie

经常有遇到说浏览器与flash之间不好debug,数据不好交流，确实每次遇到都得多写些代码。麻烦！这回我打算写个flash类，专门用来解决这些问题。这几天，我就先从cookie的读写开始，写了个cookie类，有了这个类，以后我就能直接在flash里面操作cookie了。一劳永逸，大伙如果觉得有用就拿去吧。我已经放在了google...
基于SfM计算相机姿态

具体过程为： ① 通过相机标定方法，预先计算相机的内参矩阵； ② 相邻帧特征点匹配，并结合内参矩阵计算本征矩阵； ③ 本征矩阵分解获得相机的外参矩阵[R | T]，最终的相机移动距离等于矩阵T的Frobenius范数。 #include #include
剑指offer：面试题34. 二叉树中和为某一值的路径

题目：二叉树中和为某一值的路径输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。示例: 给定如下二叉树，以及目标和 sum = 22， 5 / 4 8 ...
vector容器 begin()与end()函数、front()与back()的用法

begin函数：函数原型: iterator begin(); const_iterator begin(); 功能：返回一个当前vector容器中起始元素的迭代器。 end函数：函数原型： iterator end(); const_iterator end(); 功能：返回一个当前vector容器中末尾元素的迭代器。...
C++ STL: 容器vector源码分析

文章目录前言vector的核心接口vector push_back实现vector 的 Allocatorvector 的 push_back总结...
leetcode-102 二叉树的层次遍历

给定一个二叉树，返回其按层次遍历的节点值。（即逐层地，从左到右访问所有节点）。例如: 给定二叉树: [3,9,20,null,null,15,7] 3 / 9 20 / 15 7 返回其层次遍历结果： [ [3], [9,20], [15,7] ] 方法一（非递归）二叉树的层次遍历即二叉树的广度遍历，可以使...