一道面试时候的算法题，求答案

Question

已知有序数组A[1..N], 求在数组中是否存在A[i] = i， 如果存在，返回i值， 写出最快的算法 

Answer 1

有人知道答案吗？是否有log(n)算法存在？

Answer 2

本帖最后由 bdmh 于 2009-10-09 09:32:38 编辑

  

Answer 3

-_- 2楼.. 他说的log(n)是说算法复杂度...

Answer 4

一个例子:const
  N = 9;const
  A : array[1..N] of Integer = (0, 1, 3, 5, 7, 8, 10, 11, 12);procedure TForm1.FormCreate(Sender: TObject);
var
  i : Integer;
begin
  i := (1 + N) div 2;
  while (i >= 1) and (i <= N) do
  begin
    if A[i] < i then i := (N + i + 1) div 2
    else if A[i] > i then i := (1 + i - 1) div 2
    else break;
  end;
  if (i >= 1) and (i <= N) then
    ShowMessage ('Found at: ' + IntToStr(i))
  else
    ShowMessage ('Not found');
end;

Answer 5

const
  N = 9;const
  A : array[1..N] of Integer = (0, 3, 3, 5, 7, 8, 10, 11, 12);另外如果没有满足的,会进入死循环 

Answer 6

用二分法我觉得得不太可行
不管中间A[I]比I是否大还是小,前后俩部分都有可能出现相等的情况
如果都查一次,和直接一个循环数组没什么区别 

Answer 7

二分法不行吧。
const 
  N = 9; const 
  A : array[1..N] of Integer = (0, 2, 5, 9, 9, 9, 9, 9, 10); 这样符合条件的是2， 但是用二分法的话，就找不到结果了。

Answer 8

  i := 1;
  while i <= N do
  begin
    if A[i] <> i then
    begin
      i := A[i];
    end
    else
    begin
      // 找到;
      break ;
    end;
  end;
  if i > N then
    // 没找到
    ;这个比N好点...

Answer 9

出题者的意图A[1..N], 是有排序，而且顺序增加或减小到N的一个数组
这个题出的有歧义，说得不够清晰，正向lwmonster所言，如果数组中每个元素都一样的话，二分法无效，而这道题也就失去了意义

Answer 10

这个小例子有问题，在不存在A[i]=i的情况下，会进入死循环。
感觉 i:=(1+N)div 2 这里应该是 i:=A[N] div 2 ,其次是在没有相应项的时候如何跳出循环？

Answer 11

有趣的题目。 不知道这样可以不？ 谁有空可以把这个递归转成循环function Compare(const arr: array of Integer; b, e: Integer): Boolean;
var
  c: Integer;
begin
  Result := False;
  if b > e then Exit;
  c := (b + e) shr 1;
  if arr[c] = c then Result := True
  else if arr[c] > c then
    if Compare(arr, arr[c], e) then Result := True
    else Result := Compare(arr, b, c-1)
  else if Compare(arr, b, arr[c]) then Result := True
  else Result := Compare(arr, c+1, e);
end;

Answer 12

1、如果有序是渐增的话，先逆序，否则不用处理
2、用二分。选取中间的元素，如果中间的元素a[i] < i,则不需要考虑后面的，如果a[i] > i，则不需要考虑前面的。