Pascal二分查找函数未返回-1问题及代码优化咨询

核心错误修复 #

你的binary_search函数无法正确返回-1的根本原因有两个：

1. 比较对象错误：你拿索引middle和目标值n比较，而非数组元素L[middle]与n比较。这会导致只有当目标值恰好等于某个索引值时才会返回，完全违背二分查找逻辑。
2. 边界初始化错误：last被设置为数组总长度，但数组是0基索引，正确的last应为Sizeof(L) Div Sizeof(L[0]) - 1，否则会访问超出数组范围的元素。

修复后的binary_search函数：

Function binary_search(L : Array Of Integer; n : Integer) : Integer;
Var
  middle, first, last : Integer; // 移除未使用的i、p变量
Begin
  first := 0;
  binary_search := -1;
  last := (Sizeof(L) Div Sizeof(L[0])) - 1; // 修正边界
  While (first <= last) Do
    Begin
      middle := first + (last - first) Div 2; // 优化middle计算，避免大数溢出
      If (L[middle] = n) Then // 改为比较数组元素
        Begin
          binary_search := middle;
          Break;
        End;
      If (L[middle] < n) Then 
        first := middle + 1
      Else 
        last := middle - 1; // 合并条件，避免重复判断
    End;
End;

其他代码优化点 #

• 避免重复调用二分查找：原代码在Else块中多次调用binary_search(arr, A)，每次都会重新执行查找，浪费性能。应将查找结果存入临时变量：

  Var
    foundIndex : Integer;
  // ...
  sort(arr, 1, m);
  foundIndex := binary_search(arr, A);
  If (foundIndex = -1) Then 
    Writeln('the number isnt here')
  Else
    Begin
      For i:=0 To m-1 Do
        Begin
          If (permutarr[i] = A) Then // 修正原逻辑错误：直接比较原数组元素与目标值
            Begin
              Writeln('index : ', i);
              Break;
            End;
        End;
    End;
  

• 修正原数组索引查找逻辑：原代码中If (permutarr[i] = binary_search(arr, A))逻辑错误，binary_search返回的是排序后数组的索引而非目标值，正确逻辑应为比较permutarr[i] = A。
• 移除冗余变量：原函数中i、p变量未被使用，直接删除即可。
• 参数传递优化：部分Pascal编译器对开放数组的Sizeof处理可能存在问题，建议直接将数组长度作为参数传入binary_search，更可靠：

  Function binary_search(L : Array Of Integer; len : Integer; n : Integer) : Integer;
  Var
    middle, first, last : Integer;
  Begin
    first := 0;
    binary_search := -1;
    last := len - 1;
    While (first <= last) Do
      Begin
        middle := first + (last - first) Div 2;
        If (L[middle] = n) Then
          Begin
            binary_search := middle;
            Break;
          End;
        If (L[middle] < n) Then 
          first := middle + 1
        Else 
          last := middle - 1;
      End;
  End;
  // 调用时：
  foundIndex := binary_search(arr, m, A);
  

完整修正后的代码示例 #

Function binary_search(L : Array Of Integer; len : Integer; n : Integer) : Integer;
Var
  middle, first, last : Integer;
Begin
  first := 0;
  binary_search := -1;
  last := len - 1;
  While (first <= last) Do
    Begin
      middle := first + (last - first) Div 2;
      If (L[middle] = n) Then
        Begin
          binary_search := middle;
          Break;
        End;
      If (L[middle] < n) Then 
        first := middle + 1
      Else 
        last := middle - 1;
    End;
End;

Var
  m, A, i, foundIndex : Integer;
  arr, permutarr : Array Of Integer;

// 假设fillup和sort函数已正确实现
Procedure fillup(var arr : Array Of Integer; m : Integer);
Begin
  // 你的fillup逻辑实现
End;

Procedure sort(var arr : Array Of Integer; start, len : Integer);
Begin
  // 你的sort逻辑实现
End;

Begin
  Write('num of elements in array : ');
  Read(m);
  SetLength(arr, m);
  SetLength(permutarr, m);
  fillup(arr, m);
  For i :=0 To m-1 Do
    permutarr[i] := arr[i];
  Write('the num youre looking for : ');
  Read(A);
  sort(arr, 1, m);
  foundIndex := binary_search(arr, m, A);
  If (foundIndex = -1) Then 
    Writeln('the number isnt here')
  Else
    Begin
      For i:=0 To m-1 Do
        Begin
          If (permutarr[i] = A) Then
            Begin
              Writeln('index : ', i);
              Break;
            End;
        End;
    End;
End.

内容的提问来源于stack exchange，提问作者ichil