You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
Copy file name to clipboardExpand all lines: strings_arrays/binary_search.md
+2-4Lines changed: 2 additions & 4 deletions
Display the source diff
Display the rich diff
Original file line number
Diff line number
Diff line change
@@ -1,6 +1,4 @@
1
-
Binary Search Guide
2
-
========================
3
-
Binary search is a method for locating an element in a sorted list efficiently. Searching for an element can done naively in $O(N)$ time, but binary search speeds it up to $O(\log N)$. Binary search is a great tool to keep in mind for array problems.
1
+
Binary search is a method for locating an element in a sorted list efficiently. Searching for an element can done naively in **O(N)** time, but binary search speeds it up to **O(log N)**. Binary search is a great tool to keep in mind for array problems.
4
2
5
3
Algorithm
6
4
------------------
@@ -60,4 +58,4 @@ def binary_search(nums, key):
60
58
61
59
## Runtime and Space Complexity
62
60
63
-
Binary search completes in $O(\log N)$ time because each iteration decreases the size of the list by a factor of 2. Its space complexity is constant because we only need to maintain two pointers to locations in the list. Even the recursive solution has constant space with tail call optimization.
61
+
Binary search completes in **O(log N)** time because each iteration decreases the size of the list by a factor of 2. Its space complexity is constant because we only need to maintain two pointers to locations in the list. Even the recursive solution has constant space with tail call optimization.
0 commit comments