8086-ASSEMBLY-LANGUAGE-PROGRAMS/Source Code/Searching/binary_search.asm at main · Amey-Thakur/8086-ASSEMBLY-LANGUAGE-PROGRAMS · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
; =============================================================================
; TITLE: Binary Search Algorithm
; DESCRIPTION: Implementation of Binary Search on a sorted array of 16-bit
;              unsigned integers.
; AUTHOR: Amey Thakur (https://github.com/Amey-Thakur)
; REPOSITORY: https://github.com/Amey-Thakur/8086-ASSEMBLY-LANGUAGE-PROGRAMS
; LICENSE: MIT License
; =============================================================================

.MODEL SMALL
.STACK 100H

; -----------------------------------------------------------------------------
; DATA SEGMENT
; -----------------------------------------------------------------------------
.DATA
    ; Sorted array of elements
    ARR         DW 0005H, 0111H, 2161H, 4541H, 7161H, 8231H
    LIMIT       DW 6                     ; Number of elements
    TARGET      EQU 4541H                ; Search key

    MSG_FOUND   DB 'Element found at 1-based index: $'
    POS         DB ' _rd Position','$'
    MSG_FAIL    DB 'Element not found in the array.$'

; -----------------------------------------------------------------------------
; CODE SEGMENT
; -----------------------------------------------------------------------------
.CODE
START:
    MOV AX, @DATA
    MOV DS, AX

    MOV BX, 0                           ; Left pointer (Low)
    MOV DX, LIMIT                       ; Right pointer (High)
    DEC DX                              ; Index is 0 to (N-1)

    MOV CX, TARGET                      ; Value to search for

    ; -------------------------------------------------------------------------
    ; BINARY SEARCH LOOP
    ; Logic: While (Low <= High)
    ; -------------------------------------------------------------------------
SEARCH_LOOP:
    CMP BX, DX                          ; Check range
    JA NOT_FOUND                        ; If Low > High, target is absent

    ; Mid = (Low + High) / 2
    MOV AX, BX
    ADD AX, DX
    SHR AX, 1                           ; Result in AX (Mid index)

    ; Calculate offset: Address = BASE + (Mid * 2)
    MOV SI, AX
    SHL SI, 1                           ; Multiply by 2 for Word array

    ; Comparison
    CMP CX, ARR[SI]                     ; Compare target with ARR[Mid]
    JE  ELEMENT_FOUND                   ; Exact match
    JA  GO_RIGHT                        ; If Target > ARR[Mid], search right half

    ; GO_LEFT: High = Mid - 1
    DEC AX
    MOV DX, AX
    JMP SEARCH_LOOP

GO_RIGHT:
    ; Low = Mid + 1
    INC AX
    MOV BX, AX
    JMP SEARCH_LOOP

    ; -------------------------------------------------------------------------
    ; RESULT HANDLING
    ; -------------------------------------------------------------------------
ELEMENT_FOUND:
    ; Convert 0-based index in AX to 1-based display digit
    ADD AL, 1
    ADD AL, '0'                         ; Numerical to ASCII
    MOV POS, AL

    LEA DX, MSG_FOUND
    MOV AH, 09H
    INT 21H

    LEA DX, POS
    MOV AH, 09H
    INT 21H
    JMP FINISH

NOT_FOUND:
    LEA DX, MSG_FAIL
    MOV AH, 09H
    INT 21H

FINISH:
    MOV AH, 4CH
    INT 21H

END START

; =============================================================================
; TECHNICAL NOTES
; =============================================================================
; 1. ALGORITHM:
;    - Array must be pre-sorted for binary search to work.
;    - Complexity: O(log N). Much faster than linear search for large datasets.
;    - This implementation uses the SHL technique for fast index scaling.
; = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =