Binary Search: Difference between revisions
| (8 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
=Internal= | =Internal= | ||
* [[ | * [[Recursive_Algorithms#Divide_and_Conquer|Divide and Conquer Algorithms]] | ||
* [[Binary_Search_Trees#SEARCH|SEARCH in Binary Search Trees]] | |||
=TODO= | |||
<font color=darkkhaki> | |||
* Update from Algorithms Illuminated. | |||
* Process this: https://github.com/jwasham/coding-interview-university#binary-search | |||
</font> | |||
=Overview= | =Overview= | ||
| Line 12: | Line 19: | ||
==Sorted Arrays== | ==Sorted Arrays== | ||
For a binary search on a '''sorted''' array, we know upfront whether the number we search is in the first half or in the second half by looking at the element in the middle, so we recurse only once - we split the problem in one smaller sub-problem (a=1). The size of the subproblem is half (b=2). Upon exiting from recursion, we already have the result, so no more work is necessary in the combine phase, the combine phase is O(1) = O(n<sup>0</sup>), thus d=0. a/b<sup>d</sup> = 1/2<sup>0</sup> = 1, we find ourselves in [[Master_Method#Case_1|master method's Case 1]] of the master theorem, so the running time upper bound is O(n<sup>0</sup>log n) = O(log n). | For a binary search on a '''sorted''' array, we know upfront whether the number we search is in the first half or in the second half by looking at the element in the middle, so we recurse only once - we split the problem in one smaller sub-problem (a=1). The size of the subproblem is half (b=2). Upon exiting from recursion, we already have the result, so no more work is necessary in the combine phase, the combine phase is O(1) = O(n<sup>0</sup>), thus d=0. a/b<sup>d</sup> = 1/2<sup>0</sup> = 1, we find ourselves in [[Master_Method#Case_1|master method's Case 1]] of the master theorem, so the running time upper bound is O(n<sup>0</sup>log n) = O(log n). | ||
===Algorithm=== | |||
<font color=darkkhaki>TODO</font> | |||
==Unsorted Arrays== | ==Unsorted Arrays== | ||
<font color=darkgray>TODO</font> | <font color=darkgray>TODO</font> | ||
=Canonical Use= | |||
* [[The 2-SUM Problem]] | |||
Latest revision as of 19:11, 9 November 2021
Internal
TODO
- Update from Algorithms Illuminated.
- Process this: https://github.com/jwasham/coding-interview-university#binary-search
Overview
Binary search is the implementation of the SEARCH operation for both unsorted and sorted arrays.
In case of sorted arrays, we look at the element in the middle. If it's the element we're looking for, the algorithm finishes. If it is not, we recursively look in the left half if the element that we're looking for is smaller than the element in the middle, and in the right half otherwise. At each recurrence step the problem is divided in two, and we are only looking at the half of the problem, so the running time is O(log n). A more detailed analysis using master theorem is available below in the Running Time Analysis with Master Theorem section.
For an unsorted array, we need to look in both halves.
Running Time Analysis with Master Theorem
Sorted Arrays
For a binary search on a sorted array, we know upfront whether the number we search is in the first half or in the second half by looking at the element in the middle, so we recurse only once - we split the problem in one smaller sub-problem (a=1). The size of the subproblem is half (b=2). Upon exiting from recursion, we already have the result, so no more work is necessary in the combine phase, the combine phase is O(1) = O(n0), thus d=0. a/bd = 1/20 = 1, we find ourselves in master method's Case 1 of the master theorem, so the running time upper bound is O(n0log n) = O(log n).
Algorithm
TODO
Unsorted Arrays
TODO