文档章节

《Delphi 算法与数据结构》学习与感悟[1]: 通过 "顺序查找" 与 "二分查找" 说明算法的重要性

涂孟超
 涂孟超
发布于 2014/09/26 15:37
字数 394
阅读 12
收藏 0
点赞 0
评论 0
测试效果图:


unit Unit1;

interface

uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
  Dialogs, StdCtrls;

type
  TForm1 = class(TForm)
    Button1: TButton;
    Memo1: TMemo;
    procedure Button1Click(Sender: TObject);
  end;

var
  Form1: TForm1;

implementation

{$R *.dfm}

{顺序查找函数}
function SeqSearch(List: TStringList; const str: string): Integer;
var
  i: Integer;
begin
  for i := 0 to List.Count - 1 do
    if CompareText(List[i], str) = 0 then begin Result := i; Exit; end;
  Result := -1;
end;

{二分查找函数; 二分查找只能针对有序列表}
function BinarySearch(List: TStringList; const str: string): Integer;
var
  L,R,M: Integer;
  CompareResult: Integer;
begin
  Result := -1;
  L := 0;
  R := List.Count - 1;

  while L <= R do
  begin
    M := (L + R) div 2;
    CompareResult := CompareText(List[M], str);
    if CompareResult < 0 then L := M + 1 else
    if CompareResult > 0 then R := M - 1 else
    begin
      Result := M;
      Exit;
    end;
  end;
end;

{对比测试}
procedure TForm1.Button1Click(Sender: TObject);
var
  TestList: TStringList;
  i: Integer;
  n1,n2: Int64;
  Count1,Count2: Integer;
  s: string;
const
  num = 1000000; {准备测试百万个数据}
begin
  TestList := TStringList.Create;
  for i := 0 to num-1 do TestList.Add(IntToHex(i,8)); {准备有序的测试值列表}

  Memo1.Clear;
  Count1 := 0;
  Count2 := 0;

  {搞 10 实验}
  for i := 0 to 9 do
  begin
    {产生范围内的随机字串}
    Randomize;
    s := IntToHex(Random(num),8);

    {顺序查找}
    QueryPerformanceCounter(n1);
    SeqSearch(TestList, s);
    QueryPerformanceCounter(n2);
    Memo1.Lines.Add(IntToStr(n2-n1)+ #9);
    Count1 := Count1 + (n2-n1);

    {二分查找}
    QueryPerformanceCounter(n1);
    BinarySearch(TestList, s);
    QueryPerformanceCounter(n2);
    Memo1.Lines[i] := Memo1.Lines[i] + IntToStr(n2-n1);
    Count2 := Count2 + (n2-n1);
  end;

  Memo1.Lines.Add('----------------');
  Memo1.Lines.Add('平均值:');
  Memo1.Lines.Add(IntToStr(Count1 div 10)+ #9 + IntToStr(Count2 div 10));
  Memo1.Lines.Add('----------------');
  Memo1.Lines.Insert(0, '顺序'#9'二分');

  TestList.Free;
end;

end.

 
 
 
 
 

 

 

  
二分查找太快了, 用 GetTickCount 测试不出来, 只好使用 QueryPerformanceCounter;
另外 TStringList.Find 方法也是使用了 "二分查找" 的办法.

© 著作权归作者所有

共有 人打赏支持
涂孟超
粉丝 12
博文 2004
码字总数 14107
作品 0
深圳
程序员
送书 | 你一定能看懂的算法基础书(代码示例基于Python)

本文引自图灵教育《算法图解》 你一定能看懂的算法基础书;代码示例基于Python;400多个示意图,生动介绍算法执行过程;展示不同算法在性能方面的优缺点;教会你用常见算法解决每天面临的实际...

dqcfkyqdxym3f8rb0 ⋅ 2017/11/24 ⋅ 0

每天学习一点儿算法--二分查找

算法是什么? 算法就是完成一组特定任务的方法。 比如将大象放进冰箱需要三步: 打开冰箱 将大象放进冰箱 关闭冰箱 这就是一种算法。 如果用计算机语言来叙述,就是任何实现某种功能的代码片...

爱吃西瓜的番茄酱 ⋅ 01/07 ⋅ 0

算法-数据结构

时间复杂度 O(log n) 意味着什么? 写给小白的时间复杂度指南 查找算法的 Java 实现 查找算法的 Java 实现 两个有序数组合并成一个有序数组 用拉链法和线性探测法解决哈希冲突 用拉链法和线性...

掘金官方 ⋅ 2017/12/14 ⋅ 0

分块查找(Blocking Search)

1、定义 分块查找(Blocking Search)又称索引顺序查找。它是一种性能介于顺序查找和二分查找之间的查找方法。 2、基本思想 分块查找的基本思想是: (1)首先查找索引表 索引表是有序表,可采...

野渡书生 ⋅ 2016/04/28 ⋅ 1

JAVA基础学习总结(算法篇)

1、排序算法 关于排序算法我就不一一赘述了,建议看下这篇博客,讲的很详细。http://blog.csdn.net/hguisu/article/details/7776068 常用的排序一般是冒泡排序和快速排序。 冒泡排序的基本思...

tomcater ⋅ 2016/04/13 ⋅ 0

二分查找(Binary Search)

1、定义 二分查找又称折半查找,它是一种效率较高的查找方法。 二分查找要求:线性表是有序表,即表中结点按关键字有序,并且要用向量作为表的存储结构。不妨设有序表是递增有序的。 2、基本...

野渡书生 ⋅ 2016/04/28 ⋅ 0

Java实现的二分查找算法

二分查找又称折半查找,它是一种效率较高的查找方法。 折半查找的算法思想是将数列按有序化(递增或递减)排列,查找过程中采用跳跃式方式查找,即先以有序数列的中点位置为比较对象,如果要找...

孟飞阳 ⋅ 2016/06/14 ⋅ 0

算法之路

最近在GitHub上看到的某位学友的算法学习规划,贴过来与各位共勉。有新的内容可以文末留言补充。 学习方法 把所有经典算法写一遍 看算法有关源码 加入算法学习社区,相互鼓励学习 看经典书籍...

李序锴 ⋅ 2017/11/08 ⋅ 0

一份不错的php面试题(附答案)

一份不错的php面试题,附答案,有准备换工作的同学可以参考一下. 一、基础题 1. 写出如下程序的输出结果 <?php $str1 = null; $str2 = false; echo $str1==$str2 ? '相等' : '不相等'; $str3 ...

斑驳 ⋅ 2014/08/17 ⋅ 4

3常用二分查找程序的作业树

《树型软件工程方法》之系列博文3 常用二分查找程序的作业树 TREESOFT 目 录 3 常用二分查找程序的作业树. 1 3.1 问题需求.... 1 3.2 算法设计.... 1 3.3 作业树.... 1 3.4 遍历编程.... 2 ...

Treesoft ⋅ 2012/07/17 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

IDEA PermGen space内存溢出

解决方案: File -> Settings -> Build, Execution, Deployment / Build Tools / Maven / Runner下,找到VM Options选项,默认是空的,改为如下内容(或更大值)...

快乐的小火柴 ⋅ 14分钟前 ⋅ 0

前端常见跨域解决方案

什么是跨域? 跨域是指一个域下的文档或脚本试图去请求另一个域下的资源,这里跨域是广义的。 广义的跨域: 1.) 资源跳转: A链接、重定向、表单提交2.) 资源嵌入: <link>、<script>、<im...

临江仙卜算子 ⋅ 15分钟前 ⋅ 0

系统管理命令service

service命令用来控制系统服务的实用工具,例如启动、停止、重启和关闭系统服务,以及当前状态。当然也可以直接操作,例如/etc/init.d/mysqld restart等。 语法 service (选项)(参数) 选项...

Jpchina ⋅ 20分钟前 ⋅ 0

MySQL 联合索引的命中规则

为什么要用联合索引? 对于查询语句“SELECT T.* FROM T WHERE T.c1=1 AND T.c3=2”涉及到两列,这个时候我们一般采用一个联合索引(c1, c3);而不用两个单列索引,这是因为一条查询语句往往应...

hensemlee ⋅ 28分钟前 ⋅ 0

Spring 自动组件扫描

通常情况下都是在XML配置文件中手动声明Bean和组件的。不过Spring也可以自动扫描组件实例化Bean,这样就可以避免在XML文件中繁琐的Bean声明。 手动声明Bean: 这里不再啰嗦,就是简单地在XML...

霍淇滨 ⋅ 32分钟前 ⋅ 0

MapReduce简单需求分析-共同好友及查找互粉的情况

MapReduce的设计,最重要的是要找准key,然后制定一系列的数据处理流程。MapReduce的Map中,会把key相同的分配到同一个reduce中,对于key的选择,可以找到某个相同的因素。以下面的几个例子说...

Jason_typ ⋅ 34分钟前 ⋅ 0

springboot多数据源自动切换

SpringBoot多数据源切换,先上配置文件: 1.pom: <?xml version="1.0" encoding="UTF-8"?><project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/20......

JackyRiver ⋅ 36分钟前 ⋅ 0

Boost库编译应用

版本:Boost 1.66.0 Windows库编译 官网指南:直接执行bootstrap.bat处理文件即可,可以我却遇到一堆的问题。 环境:Windows 10 + Visual Studio 2017 Boost编译出来库命名 boost库生成文件命...

水海云 ⋅ 41分钟前 ⋅ 0

解决Eclipse发布到Tomcat丢失依赖jar包的问题

如果jar文件是以外部依赖的形式导入的。Eclipse将web项目发布到Tomcat时,是不会自动发布这些依赖的。 可以通过Eclipse在项目上右击 - Propertics - Deployment Assembly,添加“Java Build ...

ArlenXu ⋅ 41分钟前 ⋅ 0

iview tree组件层级过多时可左右滚动

使用vue+iview的tree组件,iview官网iview的tree树形控件 问题描述:tree层级过多时左右不可滚动 问题解决:修改overflow属性值 .el-tree-node>.el-tree-node_children { overflow: vi...

YXMBetter ⋅ 43分钟前 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部