Binary Search Algorithm

Tram Ho

Binary Search Algorithm

1. Place the problem

Given an array of n-element integers, sorted, find the position of any value in the array

For example, for a 10-element integer array between -20 and 20, find the position of the value 5

There are two ways to handle this problem: linear search and binary search

  • Linear search will loop through each element in the array until it finds a value, the time complexity is O (n).
  • Binary search has time complexity O (log (2) n) => This way is more optimal, faster.

2. How does Binary search work?

  • Let L be the first value of the array, R is the last value of the array, M is the value at the center of L and R.

  • We see M (1) <target (5) so the target is between 1 and 17, continue to set L and M to new position

  • the target is now in the range 2-9, we move R to a new location

  • So we have found the target after 3 steps, if using linear it takes 7 steps
  • If the target doesn’t exist in the array, it takes 3 steps to search while linear takes 10 steps to find the last position of the array.

3. Time Complexity

  • We see that the number of search elements changes by 10 -> 5 -> 2
  • If initially there are n elements, the number of elements changed will have the following generalized form

  • It takes about x + 1 = log (2) n + 1 ≈ log (2) n steps to find the target. If the array has 10,000,000 elements, it only takes about 24 steps to find the target. Whoa !!!!

4. Demo (Ruby language)

Share the news now

Source : Viblo