Linier and binary search

Question 1

How does linear search work?

Answer 1

1) Start with the first element
2) Compare the current element with the search term
3) If they match - report found and stop the search
4) Otherwise set the current element to be the next element
5) Repeat from step until Found or end of array reached

Question 2

What are the pros and cons of Linear search

Answer 2

+straight-forward to program
+data doesn’t not need to be sorted
+fine for a small dataset

-Inefficient with large datasets

Question 3

How does a binary search work?

Answer 3

1) calculate the midpoint
2) Compare item at midpoint with search
3) if equal then stop search and report found
4) if search < item at midpoint then highPtr -mid-1
5) if search > item at midpoint then lowPtr =mid+1
6) repeat from step 1 while lowPtr <=highPtr and not found

Question 4

pros and cons of binary search

Answer 4

+ fewer comparisons makes this earch faster than linear

• trickier to program
• dataset must be ordered