频道分类

delphi实现二分查找

作者:admin 来源: 日期:2019/9/24 12:37:09 人气: 标签:

 
假设表中元素是按升序排列,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功;否则利用中间位置记录将表分成前、后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表。重复以上过程,直到找到满足条件的记录,使查找成功,或直到子表不存在为止,此时查找不成功。

条件:数组必须先排好序 

优点:查找速度快,适用于不经常变动频繁查找的有序列表

缺点:插入删除困难

假设其数组长度为n,其算法复杂度为o(log(n))

function TForm1.binarySearch(a: array of Integer;n:Integer): Integer;
var
  istart, iend, middle: Integer; //定义数组开始下标 和结束下标     中间下标
begin
  istart :=Low(a);
  iend :=High(a);
  while (istart<=iend) do
  begin
    middle:=Trunc((istart+iend)/2);
    if a[middle]=n then    //如果中间位置数为该数则返回该数位置,退出循环
    begin
      Result:=middle;
      Exit;
    end
    else if a[middle]>n then iend:=middle-1  //中间位置数大于该数,则去掉后一子表 继续查询
    else if a[middle]<n then istart:=middle+1; //中间位置数小于该数,则去掉前一子表  继续查询
  end;
  Result:=-1;
end;

procedure TForm1.buttonClick(Sender: TObject);
const
  myarray:array[1..10] of Integer=(1,3,5,6,7,9,10,11,14,16);
begin
  ShowMessage(IntToStr(binarySearch(myarray,14)));
end;