Divide and Conquer Examples

The divide and conquer approach is mostly used with searching algorithms.

For example, the goal is to find the index of a sorted array of integers, it could be looped from beginning to end, until the index was found or not found at all. This approach has time complexity \(O(n)\). But if an approach like Binary Search is applied, then time complexity reduces to \(O(log_{2}(n))\).

Search Number in Array

Unit Tests

Unresolved include directive in modules/ROOT/pages/problem-solving-patterns/divide-and-conquer-examples.adoc - include::example$src/05-problem-solving-patterns/searchNum.test.ts[]

v1 naive approach

TIME COMPLEXITY: \(O(n)\) as each element of the array is inspected in turn.

SPACE COMPLEXITY: \(O(1)\) as no extra space is used.

Unresolved include directive in modules/ROOT/pages/problem-solving-patterns/divide-and-conquer-examples.adoc - include::example$src/05-problem-solving-patterns/searchNum-v1.ts[]

v2 binary search

TIME COMPLEXITY: \(log₂(n)\) as binary search is performed reducing the number of operations performed to find the index.

SPACE COMPLEXITY: \(O(1)\) as no extra space is used.

Unresolved include directive in modules/ROOT/pages/problem-solving-patterns/divide-and-conquer-examples.adoc - include::example$src/05-problem-solving-patterns/searchNum-v2.ts[]