Assume that I am going to give you a book. This time the book will have ordered page numbers unlike previous scenario (Linear search) .
First page number as 1,
Second page number as 2,
And so on.
What will you do if you ask to find page number 67.
Since the page numbers are ordered in ascending, we can do something like below,
1.Open the center page of the book.
2.if the page number is equal to 67. We are done
The page number is less than 67. (say 62)
You can leave the left part of the book which will have the page number from 1 to 62.
Follow the step 1 with the right part of the book. In this case starting page will be 63 (center + 1)
The page number is greater than 67. (say 75)
You can leave the right part of the book which will have the page number from 75 to end of the book.
Follow step 1 with the left part of the book. In this case ending page will be 74 (center - 1)
5.Do the above process until we find page number 67 or run out of page.
Binary Search: Found Case
Binary Search: Not Found Case
Here every time we are deciding either select left side or right side. Hence, it is called as binary search.
If we want to do binary search, the array should be in sorted order.