Anonymous user
Binary search: Difference between revisions
→{{header|Sidef}}
No edit summary |
|||
Line 4,118:
Usage:
<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}}==
| |||