Description
Search a sorted array by repeatedly dividing the search interval in half. Begin with an interval covering the whole array. If the value of the search key is less than the item in the middle of the interval, narrow the interval to the lower half. Otherwise narrow it to the upper half. Repeatedly check until the value is found or the interval is empty. Run time O(log n).
Algorithm Flowchart
graph TD
A1["Sorted array A\nSearch key K"]
B1["Initialize interval\nlow = 0, high = n-1"]
C1["Compute middle\nmid = low + (high-low)/2"]
C2["Compare key with A[mid]"]
D1{"Interval\nempty?"}
D2{"key ==\nA[mid]?"}
D3{"key <\nA[mid]?"}
E1["Narrow to lower half\nhigh = mid - 1"]
E2["Narrow to upper half\nlow = mid + 1"]
F1["Return mid\nFound"]
F2["Return -1\nNot found"]
A1 --> B1
B1 --> D1
D1 -->|No| C1
D1 -->|Yes| F2
C1 --> C2
C2 --> D2
D2 -->|Yes: sequential AND| F1
D2 -->|No| D3
D3 -->|Yes: sequential AND| E1
D3 -->|No: sequential AND| E2
E1 --> D1
E2 --> D1
classDef red fill:#ff6b6b,color:#fff,stroke:#c0392b
classDef yellow fill:#ffd43b,color:#000,stroke:#f59f00
classDef green fill:#51cf66,color:#fff,stroke:#40c057
classDef lightblue fill:#74c0fc,color:#fff,stroke:#4dabf7
classDef violet fill:#b197fc,color:#fff,stroke:#9775fa
classDef lavender fill:#e6e6fa,color:#333,stroke:#b19cd9
class A1 red
class B1 yellow
class C1,C2 green
class E1,E2 lightblue
class F1,F2 violet
class D1,D2,D3 lavender
Color Scheme (GLMP 6-Color)
Red
Triggers & Inputs
Triggers & Inputs
Yellow
Structures & Objects
Structures & Objects
Green
Processing & Operations
Processing & Operations
Light Blue
Intermediates & States
Intermediates & States
Violet
Products & Outputs
Products & Outputs
Lavender
Decision diamonds (AND/OR)
Decision diamonds (AND/OR)
Process Statistics
- Nodes: 11
- Edges: 12
- OR gates: 3
- Loops: 1
- AND gates: 3
- Complexity: O(log n)
Keywords
- binary search
- NIST DADS
- divide and conquer
- dichotomic search