Searching algorithms

Question 1

What is a linear search?

Answer 1

the simplest searching algorithm

Starting at the beginning of the data set, each item of data is examined until a match is made. Once the item is found, the search ends.

Question 2

What is a binary search?

Answer 2

starts at the middle of the list
if the value at the middle point is less than the value to be found, the lower half of the list is ignored and the upper half is searched
if the value at the middle is greater than the value to be found, the upper half is ignored and the lower part is searched
search moves to the middle of the remaining items and repeats until the item is found

Question 3

Why is a binary search more efficient than a linear search?

Answer 3

a binary search would require less steps to find the value

eg. if you were looking for 99/100, a liner search would take 99 steps but a binary would only take 7

Question 4

What is a downside of a binary search?

Answer 4

it only works if the list is ordered