Binary Search: Difference between revisions

From NovaOrdis Knowledge Base
Jump to navigation Jump to search
Line 5: Line 5:
=Organizatorium=
=Organizatorium=
* 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=
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).