二进制搜索无限递归

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]

你在BinarySearch上打电话给你的item，它位于列表中间。请看下面的评论，它们遵循您的函数的行为......

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