Linear and Binary Search Algorithms

• Algorithm


  A sequence of instructions that perform a specific task when followed
• A computer can only follow instructions, it can't do anything by itself
• What are the features of an Algorithm?

  • Precise (unambiguous, very clear instructions)
  • Well-defined (clear inputs and outputs)
  • Finite (can't have an infinite loop)
• A computer program is not an algorithm, it's an implementation of an algorithm
• Algorithms are abstract, they are not related to any particular system
• Pseudocode


  An informal description using keywords or votes, intended for human reading but looks like program code
• Flowchart


  A way to display algorithms using start/end symbols, processes, and decisions
• Linear search algorithm


  1. Check each element in the list to see if it matches the target

  2. Return the position if found, or indicate not found if no match
• Linear search


  A brute-force algorithm that has to check every item in the worst case
• Binary search algorithm


  1. Divide the list in half and check if the target is in the left or right half

  2. Repeat the process on the relevant half until the target is found or the list is exhausted
• Binary search


  Requires the list to be sorted, but is much more efficient than linear search
• The time complexity of linear search grows linearly with the input size, while binary search grows logarithmically</b>
• If the list is not sorted, binary search cannot be used and linear search is the only option