Search Algorithms

Question 1

What is a search algorithm (1)

Answer 1

1.) An algorithm used to find an item with certain characteristics in a list or collection of items.

Question 2

Linear/Sequential Search (4)

Answer 2

1. ) Brute force strategy.
2. ) Does not require a sorted list.
3. ) Moves sequentially through the list until the item is found.
4. ) For (lists > 8) Binary search is more efficient.

Question 3

Linear/Sequential | Big O (3)

Answer 3

1. ) Best: O(1)
2. ) Worst: O(n)
3. ) Average: O( (n+1)/(k+1) )

Question 4

Binary/Half-interval Search (2)

Answer 4

1. ) Divide and conquer.

2. ) Requires sorted list.

Question 5

Binary Search | How (3)

Answer 5

1. ) Compare element with middle element of list.
2. ) Discard half which does not contain element
3. ) Repeat until found.

Question 6

Binary | Big O (2)

Answer 6

1. ) Best: O(1)

2. ) Worst/Average: O( log2(n) )