Binary search, also known as half-interval search, logarithmic search, or binary chop, is a search algorithm that finds the position of a target value within a sorted array. Binary search compares the target value to the middle element of the array.
- Time Complexity: O(log n)
- Space Complexity: O(1)
- Applications: Best when data is sorted and large
- Founder's Name: P.F. Windley, A.D. Booth, A.J.T. Colin, and T.N. Hibbard
- It is one of the popular and daily using Searching Algorithm
- Find the middle element of the array
- Check whether the key is equal to middle element if yes then return the index and exit the program
- If the 2 step didn't run then test whether the element is less than the middle element if yes then run the step: 1 between the start to middle-1 index
- If the 3 step didn't run then test whether the element is higher than the middle element if yes then run the step: 1 between the middle+1 to the last index.
- Run the loop till the starting index is less than end index
- If the loop over and data not found then return -1 that means data doesn't exist
Note: The array should be sorted in ascending to descending order
Input: 10,20,30,40,50
Element to search: 20
Procedure:
Middle element:30 and element is less than 30 so search between start to middle -1 index
Middle element: 20 and yes the middle element is the key to found so return the index=1
Output: 1
Watch Binary Search Implementation
Solve Problem Related to Binary Search