在 Pascal 中使用 lo 和 hi 进行二进制搜索

Question

我想在 Pascal 中创建二进制搜索。我已经努力了几个小时来创建这段代码，但它仍然没有完成。有人可以帮我吗

program binSearch;
uses crt;

TYPE index=1..100;
VAR  arr:ARRAY[1..100] OF index;
var lo,hi,search,m,n:integer;

begin
write('n: ');
read(n);

     lo:=1;
     hi:=n;
     while (lo <> hi) do
     begin
           m:=(lo+hi) DIV 2;
           if (arr[m]<search) then
           lo:=m+1
           else
           hi:=m;
     end

     if (arr[lo]<> search) then
     index:=-1
     else
     index:=lo;

end.

这是我在网上找到的，但是这段代码只告诉你是否找到了用户要搜索的号码。

PROGRAM binary_search;

USES crt;
TYPE index=1..100; 
VAR  arr:ARRAY[1..100] OF index; 
VAR  mid,low,high,search:integer; 
     i,n:index; 
     found:boolean;
BEGIN 
     clrscr; 
     writeln('Binary search');
     writeln('array lengt:');
     readln(n); 
     writeln('Enter ',n,' numbers: ');
     FOR i:=1 TO n DO 
     BEGIN 
          readln(arr[i]); 
     END; 
     writeln('what number do you want to search?');
     readln(search); 
     low:=1; 
     high:=n; 
     found:=false; 
     REPEAT 
           mid:=trunc(low+high) DIV 2; 
           IF (search<arr[mid]) THEN 
           high:=mid-1; 
           IF (search>arr[mid]) THEN 
           low:=mid+1; 
           IF (search=arr[mid]) THEN 
           found:=true 
           ELSE 
           found:=false; 
     UNTIL ((found=true) OR (high<low)); 
     IF found=true THEN writeln('ELEMENT FOUND')
     ELSE writeln('ELEMENT NOT FOUND');
     readkey();
END.

Answer 1

您的代码可以轻松更改以获取找到的元素的索引（请注意，我写的是 a 而不是 因为可能有多个元素具有搜索值）：如果值相同，您只需插入比较元素的索引，这进一步改进了代码。另一个提示是你应该避免对 false/true 的布尔值进行测试：只需使用它们，即在你的代码中使用 UNTIL found OR (high<low) 而不是 UNTIL((found=true) OR (high<low))。进一步尝试避免预定义名称，如 high 或 low。这是我对您的代码的调整。如前所述，在查找元素的 the 索引时存在一些歧义：如果您在五个元素 1 2 2 3 4 中搜索值 2，则程序 returns 索引3 不是 2。

program binary_search;

uses
  crt;
type
  index=1..100;
var
  arr:array[1..100] of index;
var
  mid,ilow,ihigh,search:integer;
  i,n,fi:index;
  found:boolean;
begin
  clrscr;
  writeln('Binary search');
  writeln('array length:');
  readln(n);
  writeln('Enter ',n,' numbers: ');
  for i:=1 to n do begin
    readln(arr[i]);
  end;
  writeln('what number do you want to search?');
  readln(search);
  ilow  :=1;
  ihigh :=n;
  found :=false;
  repeat
    mid := (ilow+ihigh) div 2;
    if search=arr[mid] then begin
      //Element found, record the index in fi and break the search loop
      found := true;
      fi := mid;
      break;
    end
    else if search<arr[mid] then ihigh := mid-1
    else ilow := mid+1;
  until ihigh < ilow;
  if found then writeln('Element found, Index = ', fi)
  else writeln('Element NOT found');
  readkey();
end.

在 Pascal 中使用 lo 和 hi 进行二进制搜索

Binary search with lo and hi in pascal

pascal

freepascal