To make things easily understand, we are going to see a problem to solve in both ways of search and comparing the complexity.
Problem Statement: To find an element in the given sorted array
Given array Input: {1,2,5,9,23,42}
Search Element: 42
Sequential or Linear Search
Sequential Search is an algorithm that traverses every element of the given array and checks whether the searched element is match the current element or not. If matched then return else it will check till the end of the array.
Implementation
In the below implementation, we used a simple for loop that helps to traverse the elements and checks the current element array[i] matches with the search key or not. if matched then return the value and break the loop.
Complexity:
Best - O(1) => If the element present in the first Index itself
Worst - O(n) => If the element is present in the last Index (or) the element itself is not present in the array, so 0(n) is the complexity of the given problem
In the above example, the search key 42 is present in the last index of the array, so we have to must traverse the element till the last index, so the complexity is O(n).
Now we have a solution, but what about the complexity? If we have a million records in the array and definitely the execution time in such a case should be more and that affects the performance.
How to overcome this ?
As they already mentioned the given array is sorted, Binary Search is the best algorithm to apply here which helps to reduce the complexity.
Binary Search
Binary Search is an algorithm that helps to find the search key using the divide and conquer method. which means dividing your array into two parts(by finding the midpoint) and checking the search key is either greater than or less than or equal to the midpoint, based on that we can omit one part of the array and do the same with the remaining part of the array. Like the way, we have to conquer the search key.
Implementation
In the below example, we are searching 42 as the key in the given array.
Step1: Find the mid value of the given array
mid = start + end / 2Step2: If the midValue = searchKey; return true
Step3: If the midValue > searchKey => If true means
1) we can conclude here midValue is greater than search key and we can ignore the right side of the array from the mid value
2) So that start remains the same and the end is midValue-1Step4: If the midValue < searchKey => If true means
1) we can conclude here midValue is less than search key and we can ignore the left side of the array from the mid value
2) So that start is midValue+1 and the end remains the same
When the search key is found
Step1: Find the mid value of the given array which is 5 and check the mid value(5) > search key(42). So, As the mid value is less than the search key we can ignore the left side and keep the end whatever it is and change the start of the array as midValue+1, and the end index remains the same.
Step2: Find the mid value of the step2 which is 23 and check the mid value(23) > search key(42). So, As the mid value is again less than the search key we can ignore the left side and keep the end whatever it is and change the start of the array as midValue+1, and again the end index remains the same.
Step3: Now in this position the start, mid, and end values are the same, so check the search key is equal to the mid-value here and return.
When the search key is not found
Complexity:
Best — O(1) => When the first mid is equal to the search key.
Worst — O(log n) => If the element is present (or) the element matched with the last mid, so O(log n) is the complexity of the given problem
If you see the above table when the number of elements(n) in the array increases, the time complexity is getting reduced. And the reason is we are ignoring half of the inputs in every recursion.
So Here we can conclude
Whenever the given array is sorted, proceed with Binary Search instead of Linear search to get better performance.
Hope it gives a good view of the Linear vs Binary Search. Please write your questions for any doubts or corrections.