Binary search: Difference between revisions
Content added Content deleted
m (→{{header|Quackery}}: tweak to code) |
(→{{header|ASIC}}: Added) |
||
Line 1,482: | Line 1,482: | ||
Value 8 found at index 5 |
Value 8 found at index 5 |
||
Value 20 found at index 10 |
Value 20 found at index 10 |
||
==={{header|ASIC}}=== |
|||
<lang basic> |
|||
REM Binary search |
|||
DIM A(10) |
|||
REM Sorted data |
|||
DATA -31, 0, 1, 2, 2, 4, 65, 83, 99, 782 |
|||
FOR I = 0 TO 9 |
|||
READ A(I) |
|||
NEXT I |
|||
N = 10 |
|||
X = 2 |
|||
GOSUB DoBinarySearch: |
|||
GOSUB PrintResult: |
|||
X = 5 |
|||
GOSUB DoBinarySearch: |
|||
GOSUB PrintResult: |
|||
END |
|||
PrintResult: |
|||
PRINT X; |
|||
IF IndX >= 0 THEN |
|||
PRINT " is at index "; |
|||
PRINT IndX |
|||
ELSE |
|||
PRINT " is not found" |
|||
ENDIF |
|||
RETURN |
|||
DoBinarySearch: |
|||
REM Binary search algorithm |
|||
REM N - number of elements |
|||
REM X - searched element |
|||
REM Result: IndX - index of X |
|||
L = 0 |
|||
H = N - 1 |
|||
Found = 0 |
|||
Loop: |
|||
IF L > H THEN AfterLoop: |
|||
IF Found <> 0 THEN AfterLoop: |
|||
REM (L <= H) and (Found = 0) |
|||
M = H - L |
|||
M = M / 2 |
|||
M = L + M |
|||
REM So, M = L + (H - L) / 2 |
|||
IF A(M) < X THEN |
|||
L = M + 1 |
|||
ELSE |
|||
IF A(M) > X THEN |
|||
H = M - 1 |
|||
ELSE |
|||
Found = 1 |
|||
ENDIF |
|||
ENDIF |
|||
GOTO Loop: |
|||
AfterLoop: |
|||
IF Found = 0 THEN |
|||
IndX = -1 |
|||
ELSE |
|||
IndX = M |
|||
ENDIF |
|||
RETURN |
|||
</lang> |
|||
{{out}} |
|||
<pre> |
|||
2 is at index 4 |
|||
5 is not found |
|||
</pre> |
|||
==={{header|BBC BASIC}}=== |
==={{header|BBC BASIC}}=== |