二分法 -算法

╰半夏微凉° 2022-06-09 01:13 185阅读 0赞

二分法查找，这个算法要求数据要是有序的。

比如有这样的问题：找出一个数组中，两个数的和小于等于15，然后输出他们，否则就单独输出较大的数。

BinarySearch.cpp

\#include <iostream>  
using namespace std;  
  
void binarySearch(int \*array, int length)\{  
if(array == NULL || length == 0)  
return;  
//从小到大排序，双循环，减少比较的次数  
for(int i=1; i<length; i++)\{  
for(int j=length -1; j>=i; j--)\{  
if(array\[j\] < array\[j-1\])\{  
int temp = array\[j\];  
array\[j\] = array\[j-1\];  
array\[j-1\] = temp;  
\}  
\}  
\}  
  
int index =0;  
cout << "sorted array:";  
while(index < length)\{  
cout << array\[index++\] <<", ";  
\}  
cout << endl;  
  
int low = 0;  
int high = length -1;  
//使用二分法，计算最大和最小数的和是否<=15  
while(low < high)\{  
if(array\[low\] + array\[high\] <= 15)\{  
cout << "sum 15," << array\[low\] << "-" << array\[high\] << endl;  
low++;  
high--;  
\}else\{  
cout << "higher num :" << array\[high\] << endl;  
high--;  
\}  
\}  
\}  
  
int main()\{  
int array\[\] = \{13,7,3,12,9,14,8,11,6,2,10,1,5\};  
binarySearch(array,sizeof(array) / sizeof(int));  
return 0;  
\}

测试结果：

PC:~/algorithm$ g++ BinarySearch.cpp -o BinarySearch  
PC:~/algorithm$ ./BinarySearch  
sorted array:1, 2, 3, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14,  
sum 15,1-14  
sum 15,2-13  
sum 15,3-12  
higher num :11  
sum 15,5-10  
sum 15,6-9  
sum 15,7-8

发表评论取消回复

表情：

评论列表（有 0 条评论，185人围观）

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

相关阅读

相关 AcWing算法学习之二分法

系列文章目录第一节：快速排序和归并排序第二节：二分之整数二分和小数二分文章目录系列文章目录第一节：快速排序和归并排序第二节：

╰+哭是因爲堅強的太久メ/ 2024年03月31日 12:45/ 0 赞/ 47 阅读

相关算法：二分法---寻找H指数

![在这里插入图片描述][3e8bd4338b5140bfae7afb4d9bb2f9bd.png] 1、题目：给你一个整数数组 `citations` ，

红太狼/ 2024年03月03日 03:12/ 0 赞/ 50 阅读

相关四种排序算法+二分法查找算法

1 四种排序算法 ①快速排序 ![这里写图片描述][SouthEast] / 快速排序（二分法排序） / class Qui

客官°小女子只卖身不卖艺/ 2024年02月17日 19:52/ 0 赞/ 46 阅读

相关算法--二分法

一、思想假设待查找序列和题目的要求之间的关系是单调递增的，先取区间的中心，判断该处函数值和题目标准值的大小关系，如果函数值偏小，那么应该在中心右侧的区间继续查找；如果函

「爱情、让人受尽委屈。」/ 2022年12月25日 10:55/ 0 赞/ 109 阅读

相关查找算法——二分法

引言二分法，顾名思义，即一分为二的方法，通常用于判断在某个有序数列中是否存在某个数，由于其优秀的算法思想，时间复杂度一般都是 O(logN) ，通常要 O(N) 的遍历

傷城~/ 2022年11月13日 15:24/ 0 赞/ 239 阅读

相关 JAVA-二分法查找算法总结

二分查找算法：二分查找算法也叫折半查找算法。优点：1.比较次数少 2.查找速度快 3.平均性能好缺点：1.待查表需要是有序的 2.插入、删除困难算法原理

ゞ浴缸里的玫瑰/ 2022年06月15日 02:58/ 0 赞/ 174 阅读

相关二分法 -算法

二分法查找，这个算法要求数据要是有序的。比如有这样的问题：找出一个数组中，两个数的和小于等于15，然后输出他们，否则就单独输出较大的数。 BinarySearc

╰半夏微凉°/ 2022年06月09日 01:13/ 0 赞/ 186 阅读

相关学习回顾算法（二分法查找）

二分法查找概述二分法查找也称为折半查找，属于有序查找算法。用给定值key先和中间结点的关键字比较，中间结点把线形表分成两个字表，若相等则查找成功；若不相等，再根据key

ゞ浴缸里的玫瑰/ 2022年06月04日 04:12/ 0 赞/ 197 阅读

相关 java搜索算法——二分法查找

java搜索算法——二分法查找搜索建立在排好序的基础之上 TestSearch.java //搜索算法 public class TestSear

待我称王封你为后i/ 2022年04月06日 09:24/ 0 赞/ 196 阅读

相关算法——二分法查找（binarySearch）

二分法查找，也称为折半法，是一种在有序数组中查找特定元素的搜索算法。二分法查找的思路如下：（1）首先，从数组的中间元素开始搜索，如果该元素正好是目标元素，则搜索过程结束

素颜马尾好姑娘i/ 2021年11月26日 15:04/ 0 赞/ 315 阅读