Table of Contents

• Search algorithms are used to find a particular value inside a data structure, usually an array or list.

Binary Search

• This is the main search algorithm people use.

• Binary search works by taking in a sorted array, then comparing the value you’re looking for to the midpoint of the array. This will tell you on which half of the array the value is located. You then repeat the search only on that half, until you find the target.

    ![BinarySearchAnimation.gif](<https://s3-us-west-2.amazonaws.com/secure.notion-static.com/594682e9-ab8d-4f9b-a8df-c8029042a2dc/BinarySearchAnimation.gif>)
  

• General process

  1. Take in a sorted array, A, and a search target x.
  2. Calculate the midpoint of the array, mid.
  3. Compare x to mid.
     • If x > mid, x is on the right half of the remaining values.
       • Repeat the search, starting at the right half.
     • If x < mid, x is on the left half.
       • Repeat the search, ending after the left half.
     • If x = mid, you found the target. Return it.

• Implementation: This is an iterative implementation of binary search.

    ![BinarySearchCode.jpg](<https://s3-us-west-2.amazonaws.com/secure.notion-static.com/6e45c53d-612f-41e2-a13b-df522691b201/BinarySearchCode.jpg>)
  

  • Take in a sorted array, a[], and a search target, x.
  • Set the start and end points of the next search, low and high (2-3).
  • Calculate the new midpoint, mid, from low and high (4).
    • This is the midpoint of your next search range, not the entire array.
  • Compare the midpoint’s value to your search value (7).
    • If the search value is higher, it’ll be on the right half. Make the next search start after the midpoint (low = mid + 1) (8-9).
    • If the search value is lower, it’ll be on the left half. Make the next search end before the midpoint (high = mid - 1) (10-11).
    • If the search value is equal to the midpoint, the midpoint is the value you were searching for. Return it’s index. (13)
  • Repeat the searches until the start and end points of the search overlap (6). This means you’ve searched the entire array.

Other Search Methods

• You can search a data set efficiently by implementing it in a data structure that supports fast searching.
  • Tree
  • Hash table

Efficiency

• N is the number of elements you’re searching through, i.e. the size of your array or data structure.
• Binary search is O(LogN) in the worst and average case. This is because you’re not iterating through the entire data set, but cutting it in half repeatedly.