What can you do now?
You know for loop, right? So, you simply run a loop from start to end of the array and check given number exists or not.
So, what is the complexity? O(n)
Now, if you have multiple operations with 10^5(or more) values, then? It won't work anymore.
We need a better approach. That is a binary search.
For better understanding, let's consider a book with thousands of pages.
Now you want to open the 'K' page(lets K = 300). Now, what will you do, simply in the first attempt you will open nearly the middle page of the book.
After that compare the left page and right page, if any page is greater than the 'K'th page simply we don't need to explore those sides anymore, right? Just think about it, say you are on page 5 and you want to open page 3, do you need to explore greater than 5 pages anymore? Simply No.
Similarly for any problem binary search work like that.
First, find the middle position by taking the sum of left and right with divided by 2, means (left+right)/2;
Second, Compare with it.
Third, ignore one side and update the left and right sides with the middle value.
Complexity for binary search, O(log(n)), why?
Now you want to open the 'K' page(lets K = 300). Now, what will you do, simply in the first attempt you will open nearly the middle page of the book.
After that compare the left page and right page, if any page is greater than the 'K'th page simply we don't need to explore those sides anymore, right? Just think about it, say you are on page 5 and you want to open page 3, do you need to explore greater than 5 pages anymore? Simply No.
Similarly for any problem binary search work like that.
First, find the middle position by taking the sum of left and right with divided by 2, means (left+right)/2;
Second, Compare with it.
Third, ignore one side and update the left and right sides with the middle value.
Complexity for binary search, O(log(n)), why?
Pseudo code:
 |
| Sorce: Internet |
No comments:
Post a Comment