18 Searching Algorithms Interview Questions (SOLVED with CODE) Devs Must Know

When the list is sorted we can use the binary search (also known as half-interval search, logarithmic search, or binary chop) technique to find items on the list. Here's a step-by-step description of using binary search:

1. Let min = 1 and max = n.
2. Guess the average of max and min rounded down so that it is an integer.
3. If you guessed the number, stop. You found it!
4. If the guess was too low, set min to be one larger than the guess.
5. If the guess was too high, set max to be one smaller than the guess.
6. Go back to step two.

In this example we looking for array item with value 4:

When you do one operation in binary search we reduce the size of the problem by half (look at the picture below how do we reduce the size of the problem area) hence the complexity of binary search is O(log n). The binary search algorithm can be written either recursively or iteratively.

Linear (sequential) search goes through all possible elements in some array and compare each one with the desired element. It may take up to O(n) operations, where N is the size of an array and is widely considered to be horribly slow. In linear search when you perform one operation you reduce the size of the problem by one (when you do one operation in binary search you reduce the size of the problem by half). Despite it, it can still be used when:

• You need to perform this search only once,
• You are forbidden to rearrange the elements and you do not have any extra memory,
• The array is tiny, such as ten elements or less, or the performance is not an issue at all,
• Even though in theory other search algorithms may be faster than linear search (for instance binary search), in practice even on medium-sized arrays (around 100 items or less) it might be infeasible to use anything else. On larger arrays, it only makes sense to use other, faster search methods if the data is large enough, because the initial time to prepare (sort) the data is comparable to many linear searches,
• When the list items are arranged in order of decreasing probability, and these probabilities are geometrically distributed, the cost of linear search is only O(1)
• You have no idea what you are searching.

When you ask MySQL something like SELECT x FROM y WHERE z = t, and z is a column without an index, linear search is performed with all the consequences of it. This is why adding an index to searchable columns is important.

• Binary search requires the input data to be sorted; linear search doesn't
• Binary search requires an ordering comparison (like >, <); linear search only requires equality comparisons (=)
• Binary search has complexity O(log n); linear search has complexity O(n)
• Binary search requires random access to the data; linear search only requires sequential access
  • this can be very important - it means a linear search can stream data of arbitrary size

The idea behind linear search is to compare the search item with the elements in the list one by one (using a loop) and stop as soon as we get the first copy of the search element in the list. Now considering the worst case in which the search element does not exist in the list of size N then the Simple Linear Search will take a total of 2N+1 comparisons (N comparisons against every element in the search list and N+1 comparisons to test against the end of the loop condition).

    for (int i = 0; i < length; i++) { // N+1 comparisons
        if (array[i] == elementToSearch) { // N comparisons
            return i; // I found the position of the element requested
        }
    }

The idea of Sentinel Linear Search is to reduce the number of comparisons required to find an element in a list. Here we replace the last element of the list with the search element itself and run a while loop to see if there exists any copy of the search element in the list and quit the loop as soon as we find the search element. This will reduce one comparison in each iteration.

    while(a[i] != element) // N+2 comparisons worst case
        i++;

In that case the while loop makes only one comparison in each iteration and it is sure that it will terminate since the last element of the list is the search element itself. So in the worst case ( if the search element does not exists in the list ) then there will be at most N+2 comparisons (N comparisons in the while loop and 2 comparisons in the if condition). Which is better than (2N+1) comparisons as found in Simple Linear Search.

If the elements you would be searching in a list are NOT uniformly distributed, then you could do certain optimizations that can help you improve the efficiency of your search algorithms. For such improvements to be effective, you do need to know the characteristics of the data being searched, the frequency and also the fact that the underlying collection needs to be modifiable.

1. Most used pattern: If the likelihood of the current element being searched again is high, then move if from it's current location (say position i) to the front of the collection (say position 0). This does require moving elements from A[0, i-1] to A[1, i] to accommodate the new element at A[0].
2. The disadvantage of the above pattern is that it requires a lot of movement. One quick strategy is to move an element up on success by simply swapping the target element from position x with the first element at position 0. This eventually results in a similar pattern as the frequently searched elements bubble up to the top of the list.
3. On the other end of the spectrum, if an element is unlikely to be search again, then moving it to the end on find improves the chances of the other elements being searched.

Interpolation Search is an algorithm similar to Binary Search for searching for a given target value in a sorted array. It is an improvement over Binary Search for instances, where the values in a sorted array are uniformly distributed.

The binary search always chooses the middle of the remaining search space. On a contrast Interpolation search, at each search step, calculates (using interpolation formula) where in the remaining search space the target might be present, based on the low and high values of the search space and the value of the target. 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. The value actually found at this estimated position is then compared to the target value. If it is not equal, then depending on the comparison, the remaining search space is reduced to the part before or after the estimated position.

The idea of the interpolation formula or partitioning logic is to return higher value of pos when element to be searched is closer to arr[hi]. And smaller value when closer to arr[low].

arr[] ==> Array where elements need to be searched
x     ==> Element to be searched
low   ==> Starting index in arr[]
hi    ==> Ending index in arr[]

pos = low + [ (x-arr[low])*(hi-low) / (arr[hi]-arr[Low]) ]

When you do one operation in binary search we reduce the size of the problem by half. To answer the questions we have to answer, how many times can you divide N by 2 until you have 1? This is essentially saying, do a binary search (half the elements) until you found it. In a formula this would be this:

1 = N / 2^x

multiply by 2^x:

2^x = N

now do the log₂:

log₂(2^x)    = log₂ N
x log₂(2) = log₂ N
x 1         = log₂ N

this means you can divide log N times until you have everything divided. Which means you have to divide log N ("do the binary search step") until you found your element.

The same concept explained graphically:

Jump Search (also referred to as Block Search) is an algorithm used to search for the position of a target element on a sorted data collection or structure.

The fundamental idea behind this searching technique is to search fewer number of elements compared to linear search algorithm (which scans every element in the array to check if it matches with the element being searched or not). This can be done by skipping some fixed number of array elements or jumping ahead by fixed number of steps in every iteration.

Lets consider a sorted array A[] of size n, with indexing ranging between 0 and n-1, and element x that needs to be searched in the array A[]. For implementing this algorithm, a block of size m is also required, that can be skipped or jumped in every iteration. Thus, the algorithm works as follows:

• Iteration 1: if (x==A[0]), then success, else, if (x > A[0]), then jump to the next block.
• Iteration 2: if (x==A[m]), then success, else, if (x > A[m]), then jump to the next block.
• Iteration 3: if (x==A[2m]), then success, else, if (x > A[2m]), then jump to the next block.
• At any point in time, if (x < A[km]), then a linear search is performed from index A[(k-1)m] to A[km]

Consider the following inputs:

• A[] = {0, 1, 1, 2, 3, 5, 8, 13, 21, 55, 77, 89, 101, 201, 256, 780}
• item = 77

• The single most important advantage of jump search when compared to binary search is that it does not rely on the division operator (/).
• Jump Search is highly efficient for searching arrays especially when its only-seeks-forward behavior is favorable - its average performance makes it sit somewhere between Binary Search with its O(log n) complexity and Linear Search with an O(n) complexity.

If we assume uniform distribution of the values so we'll use simple linear interpolation. So if the values are:

1,2,3,4,5,6,7,8,9,10000000

And we search for number 9, searching using linear interpolation will go through all (excluding the first and last) the indices before finding the correct one. In such cases interpolation search will be O(n).

Classic mistake!

Even though it is calling itself correctly, it is missing the code necessary to recursively return the result. As it is written above, it will execute the recursive call to itself, but when it does find a number, it will return true on the first step back through the recursion. However, at the second step and thereafter, the code will return to the calling recursion and process the next line of code because it has no instruction to do something else. It will drop through the if(upper < lower) block and hit the return false statement. So, from there on, it will just return false back up the recursion.

The addition of one keyword, return, in two places, fixes the code:

 // recursive cases
...
    else if (key < values[mid])
    {
        return recur_search(key, values, lower, mid - 1);
    }        
    else // (key > values[mid])
    {
        return recur_search(key, values, mid + 1, upper);
    }
...