Top 24 Searching Interview Questions And Answers

Q: Which of the following algorithms would be the fastest?

Linear search takes just O ( n ) , while sorting a list first takes O ( n log n ) . Since you are going to search the list only once for a value, the fact that subsequent searches in the sorted list with a binary search takes only O ( log n ) does not help overcome the overhead of the O ( n log n ) time complexity involved in the sorting, and hence _a linear search would be more efficient for the task_.

Q: Explain some Linear Search optimization techniques

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.

Question 1

Explain what is Binary Search

Accepted Answer

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`: ![](https://upload.wikimedia.org/wikipedia/commons/thumb/6/64/Binary_search_into_array_-_example.svg/382px-Binary_search_into_array_-_example.svg.png) 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_. ![](https://dirask.com/static/bucket/1575232592915-67oY6qqQE1--binarry_search_algorithm.png)

Question 2

Explain what is Linear (Sequential) Search and when may we use one?

Accepted Answer

**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.

Question 3

What is an example of Interpolation Search being slower than Binary Search?

Accepted Answer

If we assume _uniform distribution_ of the values so we'll use simple linear interpolation. So if the values are: ```js 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).

Question 4

Write a program for Recursive Binary Search

Accepted Answer

*   The first difference is that the while loop from iterative approach is replaced by a recursive call back to the same method with the new values of `low` and `high` passed to the next recursive invocation along with `Array` and `key` or target element.
*   The second difference is that instead of returning false when the while loop exits in the iterative version, in case of the recursive version, the condition of `low > high` is checked at the beginning of the next level of recursion and acts as the boundary condition for stopping further recursive calls by returning false.
*   Also, note that the recursive invocations of `binarySearch()` return back the search result up the recursive call stack so that true or false return value is passed back up the call stack without any further processing.
* To further optimize the solution, in term of running time, we could consider implement the **tail-recursive solution**, where the stack trace of the algorithm would not pile up, which leads to a less memory footprint during the running time. To have the tail-recursive solution, the trick is to simply return the result from the next recursive function instead of further processing.

Question 5

Recursive and Iterative Binary Search: Which one is more efficient and why?

Accepted Answer

* With regard to **time complexity**, recursive and iterative methods both will give you O(log n) time complexity, with regard to input size, provided you implement correct binary search logic. * Focusing on **space complexity**: * The iterative approach is more efficient since we are allocating a constant amount `O(1)` of space for the function call and constant space for variable allocations. * There have been concerns around the recursive version regarding the function stack it is going to use. However, once you see it carefully, the recursive version is a **tail recursion**. Most of the modern compiler converts the tail recursion into iterative program. Thus, there won't be any issue regarding the usage of the function stack. **P.S.** A **tail recursion** is also a kind of recursion but it will make the return value of the recursion call as the last statement of the method. This will make the calculation occurs _before_ the recursion call and hence there is _no need to keep the stack to store the intermediate value_ when it moves to the next recursive call.

Question 6

Which of the following algorithms would be the fastest?

Accepted Answer

Linear search takes just O(n), while sorting a list first takes O(n log n). Since you are going to search the list only once for a value, the fact that subsequent searches in the sorted list with a binary search takes only O(log n) does not help overcome the overhead of the O(n log n) time complexity involved in the sorting, and hence _a linear search would be more efficient for the task_.

Question 7

Explain why complexity of Binary Search is O(log n)?

Accepted Answer

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: ![](https://i.stack.imgur.com/spHFh.png)

Question 8

What's wrong with this Recursive Binary Search function?

Accepted Answer

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:

```java
 // 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);
    }
...
```

Question 9

Compare Binary Search vs Linear Search

Accepted Answer

* 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 ![](https://s3-us-west-2.amazonaws.com/ib-assessment-tests/problem_images/binary_search.gif)

Question 10

Explain some Linear Search optimization techniques

Accepted Answer

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.

Top 24 Searching Interview Questions

Explain what is Binary Search

Explain what is Linear (Sequential) Search and when may we use one?

What is an example of Interpolation Search being slower than Binary Search?

Compare Binary Search vs Linear Search

What is a Jump (or Block) Search?

Explain why complexity of Binary Search is `O(log n)`?

Explain what is Interpolation Search

Recursive and Iterative Binary Search: Which one is more efficient and why?

Explain some Linear Search optimization techniques

What is the optimal block size for a Jump Search? Explain.

For Binary Search why do we need round down the average? Could we round up instead?

How to apply Binary Search `O(log n)` on a sorted Linked List?

Explain what is Ternary Search?

How is it possible to do Binary Search on a Doubly-Linked List in `O(n)` time?

When Jump Search is a better alternative than a Binary Search?

Why use Binary Search if there's ternary search?

Why would you ever do Binary Search on a Doubly-Linked list?

Is Sentinel Linear Search better than normal Linear Search?

Explain how does the Sentinel Search work?

What's wrong with this Recursive Binary Search function?

Write a program for Recursive Binary Search

Which of the following algorithms would be the fastest?

Explain what is Fibonacci Search technique?

Explain when and how to use Exponential (aka Doubling or Galloping) Search?

Top 24 Searching Interview Questions

Explain what is Binary Search

Explain what is Linear (Sequential) Search and when may we use one?

What is an example of Interpolation Search being slower than Binary Search?

Compare Binary Search vs Linear Search

What is a Jump (or Block) Search?

Explain why complexity of Binary Search is O(log n)?

Explain what is Interpolation Search

Recursive and Iterative Binary Search: Which one is more efficient and why?

Explain some Linear Search optimization techniques

What is the optimal block size for a Jump Search? Explain.

For Binary Search why do we need round down the average? Could we round up instead?

How to apply Binary Search O(log n) on a sorted Linked List?

Explain what is Ternary Search?

How is it possible to do Binary Search on a Doubly-Linked List in O(n) time?

When Jump Search is a better alternative than a Binary Search?

Why use Binary Search if there's ternary search?

Why would you ever do Binary Search on a Doubly-Linked list?

Is Sentinel Linear Search better than normal Linear Search?

Explain how does the Sentinel Search work?

What's wrong with this Recursive Binary Search function?

Write a program for Recursive Binary Search

Which of the following algorithms would be the fastest?

Explain what is Fibonacci Search technique?

Explain when and how to use Exponential (aka Doubling or Galloping) Search?

Explain why complexity of Binary Search is `O(log n)`?

How to apply Binary Search `O(log n)` on a sorted Linked List?

How is it possible to do Binary Search on a Doubly-Linked List in `O(n)` time?