Binary Search can be conceptually related to a Binary Search Tree (BST), when an array is sorted. But BSTs are not always balanced.
| Binary Search Tree (BST) | Sorted Array | |
|---|---|---|
| Traverse | O(n) | O(n) |
| Search | O(log n ~ n) | O(log n) with Binary Search |
| Insert | O(log n ~ n) | O(n) with Binary Search and shifting |
| Delete | O(log n ~ n) | O(n) with Binary Search and shifting |
It uses the technique of Two Pointers, but it involves middle index calculation and edge cases.
Requirements: Middle Index
https://leetcode.com/problems/binary-search
Last review: Jun 17, 2025 Next review: No need to review.
Requirements: Middle Index
O(log n)O(1)func search(nums []int, target int) int {
L, R := 0, len(nums)-1
for L <= R {
M := L + (R-L)/2
if nums[M] == target {
return M
}
if nums[M] < target { // L <= M < T, R
L = M + 1
} else { // L <= T < M < R
R = M - 1
}
}
return -1
}
Requirements: Middle Index
O(log n)O(1)func search(nums []int, target int) int {
L, R := 0, len(nums)-1
for L < R {
M := L + (R-L)/2
if nums[M] < target { // L <= M < T, R
L = M + 1
} else { // L <= T <= M < R
R = M
}
}
if nums[L] != target {
return -1
}
return L
}
https://leetcode.com/problems/guess-number-higher-or-lower/
Last review: Aug 18, 2025 Next review: No need to review.