Binary Search: Difference between revisions
Updated informal loop invariant of binary search. |
mNo edit summary |
||
| Line 16: | Line 16: | ||
high = mid - 1 | high = mid - 1 | ||
BINARY-SEARCH(A) | BINARY-SEARCH(A) | ||
}}'''Binary search''' is an algorithm concerned with the [[Searching Problem]], aiming to be trivially the most fastest in terms of time execution. We assume the list to be ordered. | }}'''Binary search'''<ref>Langfield, Sylvia; Duddell, Dave (2019). ''Cambridge International AS and A Level Computer Science Coursebook'' (2nd ed.). Cambridge: Cambridge University Press. ISBN 978-1-108-73375-5.</ref> is an algorithm concerned with the [[Searching Problem]], aiming to be trivially the most fastest in terms of time execution. We assume the list to be ordered. | ||
== Informal Analysis == | == Informal Analysis == | ||
| Line 30: | Line 30: | ||
==== Termination ==== | ==== Termination ==== | ||
The loop terminates either when the value is found initially, or if in a case that decrementing higher bound or incrementing lower bound yields to an inverted interval (the range of array becomes invalid), returning a nil value. | The loop terminates either when the value is found initially, or if in a case that decrementing higher bound or incrementing lower bound yields to an inverted interval (the range of array becomes invalid), returning a nil value. | ||
== References == | |||
<references /> | |||
Latest revision as of 01:50, 5 August 2026
This article is a stub. It might be missing pseudocode, complexity analysis, or a correctness sketch. It might need some other information which is incomplete perhaps.
- mid = ⌊ (low + high) / 2 ⌋
- if A[mid] == v:
- return mid
- if low > high:
- return nil
- if v > A[mid]:
- low = mid + 1
- BINARY-SEARCH(A)
- else if v < A[mid]:
- high = mid - 1
- BINARY-SEARCH(A)
Binary search[1] is an algorithm concerned with the Searching Problem, aiming to be trivially the most fastest in terms of time execution. We assume the list to be ordered.
Informal Analysis
Loop Invariant
Initialization
We begin by assuming a sorted array. We take the absolute median value of array, where partition happens. If it is coincided to be the exact value, the recursion terminates, showing the position or guarantees to run if this value is not met.
Maintenance
Each time the recursion happens, the lower or higher bounds are moved as seen in Line $7$ and Line $10$. This means the updated array $A[low \cdot\cdot high]$ becomes either $A[mid+1 \cdot\cdot high]$ or $A[low \cdot\cdot mid-1]$. It is guaranteed that our goal keeps running, unless the lower bound becomes higher than high bound and so the entire array is emptied.
Termination
The loop terminates either when the value is found initially, or if in a case that decrementing higher bound or incrementing lower bound yields to an inverted interval (the range of array becomes invalid), returning a nil value.
References
- ↑ Langfield, Sylvia; Duddell, Dave (2019). Cambridge International AS and A Level Computer Science Coursebook (2nd ed.). Cambridge: Cambridge University Press. ISBN 978-1-108-73375-5.