Searching algorithms are designed to check for an element or retrieve an element from any data structure where it is stored.
These algorithms are generally classified into two categories: Sequential Search: The elements are traversed sequentially and every element is checked. e.g. linear search. Interval Search: These algorithms are specifically designed for searching in sorted data-structures. e.g. binary search.
Just check out the element one by one, simple and straightforward. Time complexity: O(n). Rarely used practically because there are usually faster searching algorithms.
Search a sorted array by repeatedly dividing the search interval in half. Begin with an interval covering the whole array. If the value of the search key is less than the item in the middle of the interval, narrow the interval to the lower half. Otherwise narrow it to the upper half. Repeatedly check until the value is found or the interval is empty. Time complexity: O(log n)
Like Binary Search, Jump Search is another searching algorithm for sorted arrays. The basic idea is to check fewer elements by jumping ahead by fixed steps or skipping some elements in place of searching all elements.
- Use algorithm
Math.floor(Math.sqrt(n))(nis the length of array) to determine the step sizem. - Start at the first element and jump
msteps until the value at that position is greater than the target value. Once a value greater than the targer is found, perform a linear search.
arr = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610](16 elements). Search for 55 and the block size to be jumped is 4, you need to do the following steps:
- Jump from index 0 to 3.
arr[3] = 2, which is smaller than target number so continue next step. - Jump from index 4 to 7.
arr[7] = 13, smaller than target number, so continue next step. - Jump from index 8 to 11.
arr[11] = 89, greater than target number. - Now, since the element at index 11(89) is greater than 55, we will jump back a step to come to index 8
- Perform linear search from index 8 to 11, which is the subarray of
[21, 34, 55, 89]and get the element 55.
-
The best block size to be skipped. In the worst case, we have to do
n/mjumps and if the last checked value is greater than the element to be searched for, we performm-1comparisons more for linear search. Therefore the total number of comparisons in the worst case will be((n/m) + m-1). The value of the function((n/m) + m-1)will be minimum whenm = √n. Therefore, the best step size ism = √n. Also its time complexity isO(√n). -
Binary Search is better than Jump Search, but Jump search has an advantage that we traverse back only once (Binary Search may require up to O(Log n) jumps, consider a situation where the element to be searched is the smallest element or smaller than the smallest). So in a system where binary search is costly, we use Jump Search.
Interpolation search is an improvement over binary search for instances, where the values in a sorted array are uniformly distributed. Binary search always goes to the middle element to check, while interpolation search may go to different locations according to the value of the key being searched. For example, if the value of the key is closer to the last element, interpolation search is likely to start search toward the end side.
Time complexity: If elements are uniformly distributed, then O(log(logn)). In worse case, it can take O(n).
- In a loop, calculate the value of
posusing the formula:
pos = lo + ((x - arr[lo]) * (hi - lo) / (arr[hi] - arr[lo]))
arr[] - Array where elements need to be searched
x - The element to be searched
lo - Starting index in arr[]
hi - Ending index in arr[]
- If it is a match, return the index of the item.
- If the item is less than
arr[pos], calculate he probe position of the left sub-array. Otherwise, calculate the same in the right sub-array. - Repeat until a match is found or the sub-array reduces to zero.
Exponential search involves two steps: Find range where element is present and do binary search in the above range. Its time complexity is O(log(n));
- Find range where target value is present. How to find the range: The idea is to start with sub-array size 1, compare its last element with x, then try size 2, then 4 and so on until last element of a sub-array is not greater. Once we find an index i, we know that the element must be present between i/2 and i.
- Do binary search in the above found range.