Searching Algorithm in Java

Binary Search Algorithm Brief Information

It is a searching algorithm which is used for finding the position of required value or data within a sorted array. Indeed, it is much faster in comparison to linear search. Firstly, for using a binary search algorithm in an array or linked list, it must be sorted . And, this sorting process can be done by using any kind of sorting algorithm like selection sort and merge sort.

Working Mechanism

Binary sorting algorithm can be used only in sorted array. Moreover, this searching algorithm reduces the time complexity to 0 (Logn). Basically, after first comparison, half of the elements of an array are ignored. The algorithm for this searching method occurs recursively until required value is found in the array. Here, the whole mechanism of binary searching algorithm is explained through different steps. Let ‘x’ be the data which is to be searched in the given array or linked list.

Step 1:

First, ‘x’ is compared with the middle element of the array or linked list.

Step 2:

If ‘x’ matches with the middle element, then the mid index is returned.

Step 3:

If ‘x’ is greater than the middle element, then we know that ‘x’ lies on the right side of the middle index. So, the left part of the middle index is completely ignored, and the above steps recursively takes place.

Step 4:

But if ‘x’ is less than the middle element then we know that ‘x’ lies on the left side of the middle index. So, the right part of the middle index is completely ignored, and the above steps recursively takes place. For Example:

	0	1	2	3	4	5	6
Search 20	10	20	30	40	50	60	70
	l=0	1	2	m=3	4	5	h=6
20<40, take 1st half	10	20	30	40	50	60	70
	l=0	m=1	h=2	3	4	5	6
Found 20, return 1	10	20	30	40	50	60	70

  Let us consider an array of sorted number as shown above where number “20” is to be searched. At first highest index (let be h) and lowest index (let be l) is calculated and the mid index of the array (let be m) is calculated by the formula m = (l + h)/2. In the above example, l=0 and h=6. So, m = (0+6)/2 i.e. 3. The element of the third index i.e.40 is compared with the searched number i.e. 20. Since 20 is less than 40, the number 40 and right to 40 are ignored. Now 20 is searched among the remaining numbers i.e. [10,20,30]. For this array, l=0 and h=2. So, m = (0 + 2)/2 i.e. 1. Now, the element of the first index i.e. 20 is compared with searched number i.e. 20. Since these two numbers matched, its index i.e. 1 is returned.  

Linear Search Algorithm

Brief Information

It is the most simple and basic search algorithm in which we search an element or value in a given array or linked list by checking that element from the starting, till the desired element or value is found. Since the required value is searched by comparing with every element in the array, there is no need to sort the array. The average time complexity of linear search is given by 0(n). Although it is the most basic and simple searching algorithm, it is rarely used in comparison to binary search as binary search is significantly faster than linear search.

Working Mechanism

The working mechanism of linear search is very simple. It can be explained in the following steps: • Searching for the element starts from the leftmost element of the array or linked list and the value to be searched is compared one by one with each element of that array. • If the searched element matched with an element of that array, then the index of that element is returned. • If the searched element does not match with any of elements, -1 is returned. For Example: Finding 15 in given array.

0	1	2	3	4	5	6
10	30	20	50	40	15	32

  Let us consider, we have to search the number 15 by using linear search algorithm in an unsorted array as shown in the above figure. In linear search, the item to be searched is continuously compared with each element of the array. So, at first “15” is compared with “10”. If the searched item does not match with the element, then second element of array is compared with the searched item. In the above figure, 15 is compared with every element until fourth index. On comparing with the fifth index of the array, the searched element matches with the element of the array and the index of that element i.e. 5 is returned.