Binary Search: Difference between revisions
Jump to navigation
Jump to search
| Line 6: | Line 6: | ||
* Binary search can be applied to sorted or unsorted array. Provide time complexity analysis. | * Binary search can be applied to sorted or unsorted array. Provide time complexity analysis. | ||
=Running Time Analysis with Master Theorem= | ==Running Time Analysis with Master Theorem== | ||
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 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 Case 1 of the master theorem, so the running time upper bound is O(n<sup>0</sup>log n) = O(log n). | ||
Revision as of 18:30, 21 September 2021
Internal
Overview
Organizatorium
- Binary search can be applied to sorted or unsorted array. Provide time complexity analysis.
Running Time Analysis with Master Theorem
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 Case 1 of the master theorem, so the running time upper bound is O(n0log n) = O(log n).