Binary search: Difference between revisions
Content added Content deleted
No edit summary |
|||
Line 4,118: | Line 4,118: | ||
Usage: |
Usage: |
||
<lang ruby>say binary_search([34, 42, 55, 778], 55); #=> 2</lang> |
<lang ruby>say binary_search([34, 42, 55, 778], 55); #=> 2</lang> |
||
=={{header|Simula}}== |
|||
<lang simula>BEGIN |
|||
INTEGER PROCEDURE BINARYSEARCHREC(A, LVALUE); |
|||
INTEGER ARRAY A; |
|||
INTEGER LVALUE; ! VALUE IS A KEY WORD ; |
|||
BEGIN |
|||
INTEGER PROCEDURE SEARCH(LOW, HIGH); |
|||
INTEGER LOW, HIGH; |
|||
BEGIN |
|||
INTEGER MID; |
|||
! INVARIANTS: VALUE > A[I] FOR ALL I < LOW |
|||
VALUE < A[I] FOR ALL I > HIGH ; |
|||
MID := (LOW + HIGH) // 2; |
|||
SEARCH := IF HIGH < LOW THEN -LOW - 1 |
|||
ELSE IF A(MID) > LVALUE THEN SEARCH(LOW, MID-1) |
|||
ELSE IF A(MID) < LVALUE THEN SEARCH(MID+1, HIGH) |
|||
ELSE MID; |
|||
END SEARCH; |
|||
BINARYSEARCHREC := SEARCH(LOWERBOUND(A, 1), UPPERBOUND(A, 1)); |
|||
END BINARYSEARCHREC; |
|||
INTEGER PROCEDURE BINARYSEARCH(A, LVALUE); |
|||
INTEGER ARRAY A; |
|||
INTEGER LVALUE; ! VALUE IS A KEY WORD ; |
|||
BEGIN |
|||
INTEGER LOW, HIGH, MID; |
|||
BOOLEAN FOUND; |
|||
LOW := LOWERBOUND(A, 1); |
|||
HIGH := UPPERBOUND(A, 1); |
|||
WHILE NOT FOUND AND LOW <= HIGH DO BEGIN |
|||
! INVARIANTS: LVALUE > A(I) FOR ALL I < LOW |
|||
LVALUE < A(I) FOR ALL I > HIGH ; |
|||
MID := (LOW + HIGH) // 2; |
|||
IF A(MID) > LVALUE THEN |
|||
HIGH := MID - 1 |
|||
ELSE IF A(MID) < LVALUE THEN |
|||
LOW := MID + 1 |
|||
ELSE |
|||
FOUND := TRUE; |
|||
END; |
|||
! LVALUE WOULD BE INSERTED AT INDEX "LOW" ; |
|||
BINARYSEARCH := IF FOUND THEN MID ELSE -LOW - 1; |
|||
END BINARYSEARCH; |
|||
COMMENT ** CAUTION ** ONLY WORKS FOR ARRAY LOWER BOUND=0; |
|||
INTEGER ARRAY HAYSTACK(0:9); |
|||
INTEGER I, J, K, NEEDLE; |
|||
OUTTEXT("ARRAY = ("); |
|||
I := LOWERBOUND(HAYSTACK, 1); |
|||
FOR J := 1, 6, 17, 29, 45, 78, 79, 87, 95, 100 DO BEGIN |
|||
HAYSTACK(I) := J; |
|||
OUTINT(HAYSTACK(I), 0); |
|||
IF I < UPPERBOUND(HAYSTACK, 1) THEN OUTTEXT(", "); |
|||
I := I + 1; |
|||
END; |
|||
OUTTEXT(")"); |
|||
OUTIMAGE; |
|||
OUTIMAGE; |
|||
FOR NEEDLE:= 0, 1, 7, 17, 95, 99, 100, 101 DO BEGIN |
|||
OUTTEXT("LOOKUP RECURSIV "); |
|||
OUTINT(NEEDLE, 3); |
|||
OUTTEXT(" ... INDEX = "); |
|||
K := BINARYSEARCHREC(HAYSTACK, NEEDLE); |
|||
OUTINT(K, 3); |
|||
IF K < 0 THEN OUTTEXT(" NOT FOUND!"); |
|||
OUTIMAGE; |
|||
OUTTEXT("LOOKUP ITERATIV "); |
|||
OUTINT(NEEDLE, 3); |
|||
OUTTEXT(" ... INDEX = "); |
|||
K := BINARYSEARCH(HAYSTACK, NEEDLE); |
|||
OUTINT(K, 3); |
|||
IF K < 0 THEN OUTTEXT(" NOT FOUND!"); |
|||
OUTIMAGE; |
|||
OUTIMAGE; |
|||
END; |
|||
END</lang> |
|||
{{out}} |
|||
<pre> |
|||
ARRAY = (1, 6, 17, 29, 45, 78, 79, 87, 95, 100) |
|||
LOOKUP RECURSIV 0 ... INDEX = -1 NOT FOUND! |
|||
LOOKUP ITERATIV 0 ... INDEX = -1 NOT FOUND! |
|||
LOOKUP RECURSIV 1 ... INDEX = 0 |
|||
LOOKUP ITERATIV 1 ... INDEX = 0 |
|||
LOOKUP RECURSIV 7 ... INDEX = -3 NOT FOUND! |
|||
LOOKUP ITERATIV 7 ... INDEX = -3 NOT FOUND! |
|||
LOOKUP RECURSIV 17 ... INDEX = 2 |
|||
LOOKUP ITERATIV 17 ... INDEX = 2 |
|||
LOOKUP RECURSIV 95 ... INDEX = 8 |
|||
LOOKUP ITERATIV 95 ... INDEX = 8 |
|||
LOOKUP RECURSIV 99 ... INDEX = -10 NOT FOUND! |
|||
LOOKUP ITERATIV 99 ... INDEX = -10 NOT FOUND! |
|||
LOOKUP RECURSIV 100 ... INDEX = 9 |
|||
LOOKUP ITERATIV 100 ... INDEX = 9 |
|||
LOOKUP RECURSIV 101 ... INDEX = -11 NOT FOUND! |
|||
LOOKUP ITERATIV 101 ... INDEX = -11 NOT FOUND! |
|||
</pre> |
|||
=={{header|UNIX Shell}}== |
=={{header|UNIX Shell}}== |