Binary Search (Divide & Conquer)
Learn Binary Search (Divide & Conquer) (Divide & Conquer, Data Structures & Algorithms) with worked examples, diagrams and interview questions. Free on JavaSchoolLab.
Binary Search as Divide and Conquer Binary search is divide and conquer where the conquer step needs only one half . Compare the target with the middle element of a sorted range, then throw away the half that cannot contain it. The recurrence is T(n) = T(n/2) + O(1) , which solves to O(log n) . There is nothing to combine: the answer of the half is the answer.