tech-notes-and-questions

Searching Techniques

1. Linear Search

Also called sequential search algorithm, starts at one end and goes through each element of a list until the desired element is found.
Time Complexity: O(n) worst, O(1) best
Space Complexity: O(1)

2. Binary Search

Used in sorted arrays, repeatedly dividing the search interval in half.
Time Complexity: O(log n) worst, O(1) best
Space Complexity: O(1) {recursive call stack: O(log n)}

3. Ternary Search

Like how binary search makes 2 parts, ternary search makes 3 parts.
Time Complexity: O(log n) worst, O(1) best
Space Complexity: O(1) {recursive call stack: O(log n)}