Binary Search
A searching algorithm that is designed to search from a sorted list.
Idea:
Compare the target with the middle most value
If not found, eliminate the half where the target cannot exist
Cons/Caveat:
The database must be comparable and sortable
Algorithm Demonstration
First is a binary search and showing how itโd work
Second is a sequential search which is the same as a linear search
Complexity of Binary Search
Big O Notation:
We are splitting the dataset continuously into halves until we hit our target or not find our target.
Algorithm
Let A be a sorted array; N be length of A; T be searching target
1. Set Left=0 and Right=N-1
2. while Left <= Right:
3. Set Middle to the floor of (Left + Right)/2
4. If A[Middle] < T, set Left = middle+1 and go to step 2
5. If A[Middle] > T, set Right = middle-1 and go to step 2
6. If A[Middle] == T, return Middle as search is done
Last updated