Binary Search vs Simple Search

I have been reading Gorkking Algorithms by Aditya Y.Bhargava. The book is one of the most interesting and enjoyable books about algorithms, so I thought I would share insights from each chapter.

Chapter one is mainly about the differences between simple search and binary search, the differences are as follow:

  “study case searching for number 10 in a list of 10 elements”

• simple search would loop on each element check if it is number 10 in case number 10 is the last element we would loop 10 times to reach our element …. what is the list is 1000,000 elements?

• Binary search is one of the searching algorithms that requires a sorted list as an input and outputs the location of the required element or null if doesn’t exist.

• Binary search works as follow => “we are still working on our 10 elements list”
1. Low => 0   first element of the list
2. high => length(list) – 1  the last element of the list
3. mid => (low + high) / 2
• check if number 10 is equal to mid if yes … Congratulations number 10 is found
• if number 10 is greater than mid … update low value to mid and recalculate mid value
• if number 10 is less than mid update high value to mid and recalculate mid value 
  “IN THIS STEP WE ELIMINATED THE LIST BY HALF”
• Repeat the past two steps until 10 is found.

• binary search would find an element in a list of 10 elements in only 3 steps if the element is the last element… if it is a list of 1000,000 elements it would take 20 steps only.

• simple search complexity according to big O notation is O(n).

• binary search complexity is O(log n).