Binäre Suche unendliche Rekursion

Question

Ich habe einfachen Code in Matlab für die binäre Suche geschrieben. Es funktioniert ordnungsgemäß, wenn das gesuchte Objekt im Array ist, aber wenn nicht, geht es in eine unendliche Rekursionsschleife.

Ich bin mir nicht sicher, wo das Problem liegt.

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

Stellen Sie sich das wirklich einfachen Fall, dass Sie nur zwei Elemente in der Liste haben

A = [1 3] 

und rufen Sie Ihre BinarySearch auf einem item, die in der Mitte der Liste liegen würde. Schauen Sie sich die Kommentare unten, die folgen, wie Sie Ihre Funktion verhält ...

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 

Wenn Ihr item zu klein

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 

war

Ebenso für eine item, der größer ist als alle in der Liste enthalten ist,

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

Sie überprüfen immer wieder die gleiche Region, weil Sie links (beg) und rechts (last) Indizes dürfen beide gleich bleiben.

---

Lassen Sie uns neu implementieren die Funktion, einen tatsächlichen Wert zurückkehrt, anstatt nur die Position auch auf der Konsole ausdrucken. Die Kommentare beziehen sich direkt auf die nummerierten Schritte in der Wikipedia article for binary search, die in ihrer Struktur ähnlich sieht, was Sie versucht haben:

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 

Tests mit A wie zuvor:

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 

Beachten Sie, dass es nicht sein kann, am effizientesten, um dies rekursiv zu implementieren. Ich werde es als Übung verlassen, aber dies könnte leicht mit einer while Schleife statt implementiert werden. Die gleiche logische Struktur würde verwendet werden.

Answer 2

Versuchen Sie, Haltepunkte zu setzen, um Werte zu untersuchen, bei denen Sie ein Problem vermuten.

Sie können die while-Schleife und den break-Befehl verwenden, um zu vermeiden, in die Endlosschleife zu gehen.

Zum Beispiel versuchen, etwas wie folgt aus:

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