Binary Search: Difference between revisions
| Line 9: | Line 9: | ||
==Running Time Analysis with Master Theorem== | ==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(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). | ||
===Unsorted Arrays=== | |||
<font color=darkgray>TODO</font> | |||
Revision as of 21:01, 12 October 2021
Internal
Overview
Binary search is the implementation of the SEARCH operation for both sorted and unsorted arrays. In case of sorted arrays, because we know that once the problem is divided in two, the key we aim for can only be in just one half of the array, the running time is O(log n). For an unsorted array, we need to look in both halves.
Organizatorium
- Binary search can be applied to sorted or unsorted array. Provide time complexity analysis.
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).
Unsorted Arrays
TODO