Welcome learners, This post What is Binary search? will let you know about the binary search algorithm and helps you understand it easily. You can refer to my previous about about DSA if needed.
So what is binary search?
Binary search algorithm finds the given key element in the array. Linear search is also a searching algorithm. This algorithm also search for an element. Linear search is a process of comparing every element in the array with the given key element and it returns the position of the element if found. But binary search is different from the linear search. It is more efficient. But it requires the array to be sorted one.
Here the main idea behind binary search is, as we are using sorted array and if we found an element which is less than key element, our required element must be after it. And in the same way, if we found an element which is greater than key element, our required element must be before it. Binary search algorithm use this ideology. you need to start with the middle element and repeat this until you find your key.
Explanation
To explain it
Let us consider an example
0 1 2 3 4 5 6 7 8
array : 1 2 3 4 5 6 7 8 9
key=8
low=0
high=8
mid=(low + high)/2=4
Approach
1 2 3 4 5 6 7 8 9
so our mid element is 5. if we want to search for 8 (key=8) , we know that our element will definitely lie after our mid element 5, so our concentration or area is decreased and is set to the elements after the element five.
So we set our low value to index mid+1
i.e. low= mid+1=5
so our mid will be (5 + 8) / 2 = 6.5 ~= 6
1 2 3 4 5 6 7 8 9
So the element at 6th index is 7. It is less than 8 and our element 8 will be after it.
So low =mid+1
i.e. low= 7
mid= ( 7 + 8 ) / 2= 7.5 ~= 7
1 2 3 4 5 6 7 8 9
So we found our key at the index 7.
Binary search works in this way
Implementation
Recursive
Practice problems
