`
kmplayer
  • 浏览: 508953 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

代码调优:二分搜索

 
阅读更多
1,先给出一个经常用到的代码:
#include<iostream>
using namespace std;

int binarySearch1(int t, int data[], int n)
{
	int l = 0;
	int u = n - 1;
	int p, m;
	while (true)
	{
		if (l > u)
		{
			p = -1;
			break;
		}
		m = (l + u) / 2;
		if (data[m] < t)
			l = m + 1;
		else if (data[m] == t)
		{
			p = m;
			break;
		}
		else
			u = m -1;
	}
	return p;
}

int main()
{
    int data[]={1,4,4,5,6,8,9,9,9,9,9,10};
    int n=sizeof(data)/sizeof(data[0]);
    cout<<binarySearch1(9,data,n)<<endl;
    return 0;
}

缺点:
(1)每次循环至少需要比较两次;
(2)如果t多次出现,那么上述代码可能返回t的任意一个位置.

2,下面改进的代码,可以保证返回t第一次出现的位置.
#include<iostream>
using namespace std;

int binarySearch2(int t, int data[], int n)
{
	int l = -1;
	int u = n;
	int m;
	while ( (l + 1) != u)
	{
		m = (l + u) / 2;
		if (data[m] < t)
			l = m;
		else
			u = m;
	}
	int p = u;
	if ((u >= n) || (data[u] != t))
		p = -1;
	return p;
}

int main()
{
    int data[]={1,4,4,5,6,8,9,9,9,9,9,10};
    int n=sizeof(data)/sizeof(data[0]);
    cout<<binarySearch2(9,data,n)<<endl;
    return 0;
}


3,继续改进,循环展开将会有很大的提高.
#include<iostream>
#include<algorithm>
#include<iterator>
using namespace std;

const int N=1000;
int data[N];

int randInt()
{
    return rand()%(5000);
}

//这里设定数组的大小为1000
int binarySearch3(int t,int data[],int n)
{
    //第一步先保证搜索的范围为2的指数次.
    int i=512;
    int l=-1;
    if(data[511]<t)
        l=1000-512;
    while(i!=1)
    {
        if(data[l+i/2]<t)
            l=l+i/2;
        i=i/2;
    }
    //assert:i==1;data[l]<t;data[l+i]>=t
    int p=l+1;
    if(p>=n||data[p]!=t)
        p=-1;
    return p;
}

int binarySearch4(int t,int data[],int n)
{
    //第一步先保证搜索的范围为2的指数次.
    int l=-1;
    if(data[511]<t)
        l=1000-512;
    if(data[l+256]<t) l+=256;
    if(data[l+128]<t) l+=128;
    if(data[l+64]<t) l+=64;
    if(data[l+32]<t) l+=32;
    if(data[l+16]<t) l+=16;
    if(data[l+8]<t) l+=8;
    if(data[l+4]<t) l+=4;
    if(data[l+2]<t) l+=2;
    if(data[l+1]<t) l+=1;
    //assert:i==1;data[l]<t;data[l+i]>=t
    int p=l+1;
    if(p>=n||data[p]!=t)
        p=-1;
    return p;
}
int main()
{
    generate(data,data+N,randInt);
    sort(data,data+N);
    copy(data,data+N,ostream_iterator<int>(cout," "));
    cout<<endl;
    cout<<binarySearch3(447,data,N)<<endl;
    cout<<binarySearch4(447,data,N)<<endl;
    return 0;
}


分享到:
评论

相关推荐

    软件性能测试调优

    ### 软件性能测试调优 #### 一、性能测试概述 性能测试是一种软件测试类型,旨在评估软件系统的性能特点。它可以帮助我们了解软件在特定条件下的行为,包括响应时间、吞吐量、资源使用情况等关键指标。性能测试的...

    Python金融大数据风控建模实战:基于机器学习源代码.zip

    - 模型调优:使用网格搜索、随机搜索等方法调整超参数,以提高模型性能。 4. **模型评估**: - 二分类指标:准确率、查准率、查全率、F1分数、AUC-ROC曲线等。 - 多分类指标:混淆矩阵、Kappa系数、多类F1分数等...

    LibSVM-2.6程序代码注释

    3. 参数调优:LibSVM提供了一种基于网格搜索的参数调优方法,通过交叉验证在多个参数组合中寻找最佳性能的模型。主要的参数包括惩罚系数C(控制误分类的程度)和核函数的参数γ(影响模型复杂度)。 4. 训练与预测...

    编程珠玑源代码

    2. 算法:源代码中包含排序算法(如冒泡排序、选择排序、插入排序、快速排序、归并排序、堆排序)、查找算法(如顺序查找、二分查找、哈希查找)以及图算法(如深度优先搜索、广度优先搜索)。这些算法是解决问题的...

    java编程规范,包含命名、代码格式、代码优化、注释等

    5. 优化算法:使用更高效的算法,如使用二分查找代替线性搜索。 6. 并发处理:在多线程环境下,合理使用synchronized关键字和并发工具类,保证线程安全。 7. 编译器优化:启用Java编译器的优化选项,如开启逃逸...

    boston预测实战以及线性回归基础代码大全.zip

    5. 参数调优:可能包含网格搜索或随机搜索来优化模型参数。 五、模型选择与比较 除了线性回归,还有其他回归模型可供选择,如岭回归、Lasso回归、 Elastic Net等,它们通过正则化处理过拟合问题。这些模型的代码...

    机器学习matlab源代码.zip

    2. 实践应用:通过实际运行代码,可以对数据进行预处理、模型训练、评估和调优,提升实践能力。 3. 模型比较:对比不同算法的实现,有助于选择适合特定问题的最优模型。 四、代码结构与解读 每个机器学习算法的...

    龙曲良《TensorFlow深度学习》学习笔记及代码,采用TensorFlow2.0.0版本.zip

    3. 参数调优:网格搜索、随机搜索等方法,寻找最优超参数组合。 通过龙曲良的《TensorFlow深度学习》学习笔记和代码,读者可以系统地学习深度学习的基础知识,理解TensorFlow 2.0.0的使用,并通过实践提升自己的...

    机器学习例子(Python代码)

    4. 模型评估与调优:交叉验证、网格搜索等方法的使用,以提高模型的泛化能力。 5. 特征工程:包括特征缩放、特征选择和特征提取等,以增强模型的性能。 6. 模型保存与加载:如何将训练好的模型保存到文件,并在需要...

    性能调优方案arthus

    例如,使用百度搜索引擎查询“性能调优”,页面完全加载完毕所需的时间就是该操作的响应时间。 **2.2 吞吐量(TPS)** 单位时间内完成的任务数量,例如每秒处理的请求数量。对于服务大量用户的系统而言,吞吐量是...

    SVM源代码,实现了几种不同类型的SVM分类器

    3. 参数调优:通过网格搜索或交叉验证选择最佳的C和γ参数。 4. 预测:利用训练好的模型对新数据进行分类或回归预测。 七、libsvm扩展应用 libsvm不仅适用于传统的二分类和回归任务,还可以与其他算法结合,如集成...

    svm多分类的java源码

    4. 参数调优:熟悉网格搜索、交叉验证等方法,找到最佳的模型参数。 5. 分类评估指标:如准确率、精确率、召回率、F1分数等,用于评估模型性能。 如果你计划在自己的项目中使用这个Java SVM多分类源码,首先,阅读...

    7.MATLAB分类与判别模型代码 基于SVM神经网络的葡萄酒种类识别代码.zip

    6. 参数调优:通过网格搜索或随机搜索等方法调整模型参数,以优化模型性能。 7. 结果可视化:绘制混淆矩阵、ROC曲线等图表,直观展示模型效果。 总之,这个MATLAB代码示例为我们提供了一个实践SVM和神经网络分类...

    机器学习代码

    - 超参数调优:网格搜索、随机搜索、贝叶斯优化等方法用于找到最佳模型参数。 - 正则化:防止过拟合,如L1和L2正则化。 - 模型验证:交叉验证、留一法等确保模型泛化能力。 4. **数据预处理** - 缺失值处理:...

    邹博机器学习24课PPT和代码.rar

    9. 模型评估与调优:讲解交叉验证、网格搜索、模型选择等技巧。 10. 实战项目:结合具体案例,如手写数字识别、文本分类等,进行机器学习项目的实施。 三、PPT内容解析 PPT演示文稿通常包含每节课的关键知识点、...

    SVM_代码_rhythmwzj_

    代码可能包含了网格搜索或随机搜索等参数优化方法。 3. 分类评估:为了验证模型的性能,代码可能会包含交叉验证和各种评估指标,如准确率、召回率、F1分数等。 总结来说,rhythmwzj的SVM代码实现为学习者提供了一个...

    《机器学习实战》基于python3.6的代码实现.zip

    - 模型选择:通过网格搜索或随机搜索找到最佳参数组合。 - 评估指标:如准确率、精确率、召回率、F1分数、AUC值等,用于衡量模型性能。 5. 特征工程: - 特征缩放:如标准化和归一化,确保不同特征在同一尺度上...

    机器学习笔记和算法的python代码实现,学习的课程包括Andrew Ng 和林轩田的Machine Learnin.zip

    2. 超参数调优:网格搜索、随机搜索等方法来寻找最优的模型参数。 3. 模型融合:集成学习如Bagging、Boosting和Stacking,提高模型的泛化能力。 五、深度学习 1. 深度神经网络(DNN):多层神经网络,用于图像识别...

    模式分类第二版Duda 英文版 参考答案及matlab代码

    - **网格搜索**或**随机搜索**:用于调优模型参数,以提高分类效果。 通过学习和实践这些MATLAB代码,读者不仅可以深化对模式分类理论的理解,还能提升编程技能,为实际项目开发打下坚实基础。同时,这些代码也可以...

    svm.rar_svm 源代码_svm模型_visual c

    5. 超参数调优:可能使用网格搜索或随机搜索等方法,寻找最佳参数组合。 6. 验证和评估:在测试集上进行预测,计算准确率、精确率、召回率等指标,评估模型性能。 7. 应用模型:保存模型以便后续预测新数据。 在...

Global site tag (gtag.js) - Google Analytics