1. What is a Search Algorithm?
Linear search algorithms checks each and every value linearly, starting from the beginning element.
Binary(half interval searches), repeatedly compares the middle element of the structure and with each step, it divide the search space in half.
Comparison search algorithm is an improvisation on linear search algorithm because it successively eliminates the records which are produced by the comparisons of the keys, until the target record is found, Thus, it can be applied on data structures with a defined order.
Digital search algorithms mainly based on the properties of digits in data structures.
Linear search starts at the beginning of data structure and checks each value until it get the target value whereas In binary search, the starting point is the middle of a sorted list and determines which side is the target value. Even in terms of time complexity, Binary search is better than linear search. The time complexity for worst case in Binary search is O(log n) whereas in Linear search, it is O(n). But, we can perform binary search only in sorted list of items.
Binary Search is an efficient search algorithm that finds the target value from an ordered list. It compares the target value to the middle element of the list. If they are not equal, then the half portion of list is eliminated in which the target value cannot lie and it repeatedly divides the remaining half until it finds the desired value. Binary search is based on divide and conquer strategy to find a value within a list which is already sorted. In next section, we'll briefly explain Divide and Conquer strategy in algorithms.
Divide and Conquer is a powerful tool for solving sophisticated problems. The main idea is to break down a problem recursively into two or more sub problems, until it becomes easy enough to be solved directly. And then, the solution to the sub problems are combined to produce a solution to the original problem. For understanding Divide and Conquer algorithm, you need to understand the nature of the problem to be solved. In case of Binary Search Algorithm, Divide and Conquer strategy applied in the form of dividing a problem into only one sub-problem. In this case, it is more efficient algorithm as compared to the general divide and conquer algorithm. The important application of Divide and Conquer algorithm is in Prune and Search, it is a method of solving optimization problems. In prune and search, at each step, the search space is pruned by a constant factor, the algorithm has the same complexity as the pruning step and the constant depends on the pruning factor.
The main requirement for Binary Search is that the array being already sorted.
1. We have an array 'A' of size, N and 'x' is the target value.
We'll define two variable, 'low' being the lowest position of array and 'high' being the highest position of array.
Eliminate the half portion where the value cannot lie.
4. Repeat it, until you get the value.
Binary Search can be done Iteratively as well as recursively.
The values written above array are index of the corresponding items.
As, we explained earlier, low represents the lowest index and high gives the highest index of array. N represents the size of array and x denotes the value we want to search in the array.
Now , we'll compare the value in index 'mid' with 'x'.
Eliminate the first half. That'll make the value of low 5 that is mid+1, keeping the value of high same.
We are again comparing the value in index 'mid' with 'x'.
Eliminate the portion from mid+1 to high. That'll make the value of high 5, keeping the value of low same.
3. A[mid]=44, which is equal to target value.
So, the position of target value is 5.
Suppose we have an array A and we are searching 'x' in this array, if it is not sorted then we have to perform linear search and that 'll take O(n) time. But if A is a sorted array, there is a much faster way, that is Binary Search.
The analysis of binary search can be done in three type of comparisons. These are best case, worst case and average. Let N be the size of array A. Binary Search as we discussed earlier can be performed recursively as well as iteratively and in both the cases, the number of comparisons are same.
Now, we'll explain all the three cases of comparisons.
Best case: The time complexity of best case is O(1). This is called Big O Notation. In this case, the value we are searching is the middle in the array. So only one comparison is needed for finding it. Thus, the time complexity is O(1).
Worst Case: Generally, when we analyse the time complexity of any algorithm, it is given by its worst case. That is why, the time complexity of binary search algorithm belongs to O(log n) class. It represents that the asymptotic growth of time the function is taking to execute when an input size 'n' is given will not be greater than log n. In this case, the item does not exist at all.
Average case: We'll first calculate the number of comparisons that are required to find each element and the probability of searching for that element and then doing the sum over the product of the above two entities we calculated. To simplify this, we assume that we are not taking the case in which the value we are searching is not in array and the probabilities of searching each element is uniform.
This difference became extremely significant when N is large.
For example, suppose the array contains 2 billion values. Linear search would require about a billion comparisons whereas binary search can do it in only 32 comparisons.