2.1 | Algorithms | 2.1.4

2.1 | Algorithms | 2.1.4

1. Searching Algorithms

   • A search algorithm is a set of instructions for finding a specific item of data within a data set.
   • Computer systems can store and process billions of pieces of data so it is vital that computers can find the information they need efficiently.
   • Effective searching
     • An effective search is one which will always either find the solution or determine that the target data is not present.
     • An efficient search will find the solution quickly regardless of its location within the data set.
   • Examples of search algorithms
     • There are two common search algorithms.
       • Linear search.
       • Binary search.

2. Linear Search

   • Linear search is one of the simplest searching algorithms.
   • The concept
     • If you were looking for a specific piece of paper in a stack of papers, then one way to find it would be to work from the top of the stack to the bottom, checking each paper on the way.
       • This is exactly how linear search works.
   • In English
     • 1. Check the first item in the data set. If it is what we are looking for, return it.
       • 2. Check the second item in the data set. If it is what we are looking for, return it.
         • 3. Continue for rest of items.
           • 4. If we reach the end of the data set, then the item was not in our data set.
   • Pros and cons of linear search
     • + Very easy to implement.
     • - Slow on a long list.

3. Binary Search

   • Binary search is an example of a divide-and-conquer algorithm.
   • The concept
     • If you try to find a certain page in a book, it's unlikely that you check every page on the way.
       • You are more likely to split the book in two, then see if the page you need is before or after the split, and repeat.
         • This is the concept behind the binary search.
   • In English
     • 1. Find the middle of the data set.
     • 2. If the middle value is greater than the target then repeat on the first half of data set.
     • 3. If the middle value is lesser than the target then repeat on the second half of data set.
     • 4. If the middle value is the target - we found it!
     • 5. Stop repeating once the size of our data set is zero.
   • Pros and cons of binary search
     • + Faster than linear search on a large data set.
     • - Data set must be sorted before starting.