二分查找无限递归

Question

我已经在 Matlab 中为二进制搜索编写了简单的代码。如果搜索到的项目在数组中，它就可以正常工作，但如果不在数组中，它就会进入无限递归循环。

我不确定问题出在哪里。

function [] = BinarySearch(A,beg,last,item)
mid=floor((last+beg)/2);
if (beg)<=last
    if item==A(mid)
        fprintf('Item found at position %d \n',mid);
    else    
        if(item<A(mid))
            BinarySearch(A,beg,mid,item)
        else
            BinarySearch(A,mid,last,item)
        end    
    end
else
     fprintf('Item not found\n');
end

Answer 1

想象一下您的列表中只有 2 项的非常简单的情况

A = [1 3]

然后您在 item 上调用您的 BinarySearch，它位于列表的中间。查看下面的评论，这些评论遵循您的函数的行为方式...

BinarySearch(A, 1, 2, 2)
% mid = 1
% item ~= A(1): go to else
% item >  A(1): go to else
% BinarySearch(A, 1, 2, 2)
% ... rinse and repeat

如果你的item太小

BinarySearch(A, 1, 2, 0)
% mid = 1
% item ~= A(1): go to else
% item <  A(1)
% BinarySearch(A, 1, 1, 0)
%  mid = 1
%  beg <= last (this is still true)
%  item ~= A(1): go to else
%  item <  A(1)
%  BinarySearch(A, 1, 1, 0)
%  ... rinse and repeat

类似地，对于比列表中任何一个都大的 item，

BinarySearch(A, 1, 2, 5)
% leads to BinarySearch(A, 1, 2, 5)
% ... repeat!!

您一直在重新检查同一个区域，因为您的左 (beg) 和右 (last) 索引可以保持不变。

让我们重新实现该函数，返回一个实际值，而不是仅仅将位置也打印到控制台。评论直接与 Wikipedia article for binary search 中的编号步骤相关，它在结构上与您尝试的类似：

function idx = BinarySearch(A, L, R, item)
%% BINARYSEARCH search for an item in the array A. Assumes that A is sorted ascending
% 1. Should be initially called using idx = BinarySearch(A, 1, n, item)
% where n is the number of elements in A, numel(A)
    % 2. if L > R, the search terminates as unsuccessful
    if L > R
        idx = 0;
    else
        % 3. set m (position of middle element) to the floor of (L+R)/2
        m = floor((L+R)/2);
        % 4. if Am < item, set L to m+1 and go to 2.
        if A(m) < item
            L = m + 1; % YOU MISSED THIS STEP, CAUSING OVERLAPPING SEARCH REGIONS
            idx = BinarySearch(A, L, R, item);
        % 5. if Am > item, set R to m-1 and go to 2.
        elseif A(m) > item
            R = m - 1; % THE OTHER HALF OF THE STEP YOU MISSED
            idx = BinarySearch(A, L, R, item);
        % 6. Now Am = item, search is done, return index
        else 
            idx = m;
        end
    end
end

像以前一样使用 A 进行测试：

BinarySearch(A, 1, 2, 2); % returns 0: not found
BinarySearch(A, 1, 2, 0); % returns 0: not found
BinarySearch(A, 1, 2, 5); % returns 0: not found
BinarySearch(A, 1, 2, 3); % returns 2: 3 is at index 2
BinarySearch(A, 1, 2, 1); % returns 1: 1 is at index 1

请注意，递归实现它可能不是最有效的。我将把它留作练习，但这可以使用 while 循环轻松实现。将使用相同的逻辑结构。

Answer 2

尝试设置断点以检查您认为可能存在问题的值。

您可以使用 while 循环和 break 命令来避免进入无限循环。

例如尝试这样的事情：

function [index] = binarySearch(A, n, num)

left = 1;
right = n;
flag = 0;

while left <= right
   mid = ceil((left + right) / 2);

if A(mid) == num
    index = mid;
    flag = 1;
    break;
else if A(mid) > num
    right = mid - 1;
    else
        left = mid + 1;
     end
  end
end

  if flag == 0;
  index = -1;
  end

end

二分查找无限递归

Binary search infinite recursion

search

matlab

binary-search