Searching MCQ Quiz in मराठी - Objective Question with Answer for Searching - मोफत PDF डाउनलोड करा

It is the worst case scenario of binary search.

The worst case for binary search is when the value x is not in the set L as then the algorithm has to perform the maximum possible number of recursive calls, and hence the maximum possible number of operations.

Therefore, the worst case time complexity of binary search is O(logn).

The correct answer is Hashing.

This question can be solved by some basic understanding of every type of search.
Let's go one by one -

Binary searching:- In binary searching, you have a sorted array, and you divide that array according to the mid element, Then either you have to go left or right and search till the end until you find the required element. 
This involves unnecessary comparison. So, option 1 got eliminated.

Sequential searching:- Here, This searching technique involves Finding a particular value in a list that consists of Checking All of its elements, one at a time and in sequence until the desired element is found. 
This involves unnecessary comparison, so, option 2 got eliminated.

Hashing-It is the best searching technique available with O(1) time complexity, it has a table consisting of key-value pairs, and directly with the help of key u can reach to value. 
So, no unnecessary comparison is needed, 
Refer to the below diagram to understand it better 

So, option 3 will be the answer here 

The correct answer is option 1.

Concept:

Linear search:

A linear search, often known as a sequential search, is a technique for locating an element in a list. It systematically verifies each element of the list until a match is discovered or the entire list has been searched.

Algorithm:

linear_search(int a[], int n, int X)

{ 
  for (int i = 0; i < n; i++)  
    {  
        if (a[i] == X)  
        return i+1;  
    } 

}

Explanation:

Best case:

The best case in the Linear Search Algorithm happens when the item to be found is at the beginning of the Array. If the element is found at starting of the array the linear search successful and comes out from the loop. Hence this behavior takes less time when compared to other behaviors.

Worst-case:

In the Linear Search Algorithm, the worst-case scenario happens when the item to be found is at the end of the Array or the element is not present in the array. Hence the linear search compares each element till the end. So it takes maximum time behavior in linear search.

Average case:

In the Linear Search Algorithm, the average scenario happens when the item to be found is somewhere in the center of the Array.

Hence the correct answer is a searching element is at beginning of the array.

Key Points

 The average number of comparisons in a sequential search is \({(N+1)} \over 2\) where N is the size of the array.

If the element is in the 1st position, the number of comparisons will be 1,

the element is in the 2^nd position, the number of comparisons will be 2,

the element is in the 3^rd position, the number of comparisons will be 3,

the element is in the 4^th position, the number of comparisons will be 4, .....

if the element is in the last position, the number of comparisons will be N.

So Total number of comparisons are= (1+2+3+4+5+...+N)

The total number of comparisons are=\({N(N+1)} \over 2\)

The average number of comparisons in a sequential search is \({N(N+1)} \over 2 \times N\)

Hence the correct answer is \({(N+1)} \over 2\)

Formula:

Expected number of probes in unsuccessful search = \(\frac{1}{{1 - p}}\)

Expected number of probes in successful search = \(\frac{1}{p}\ln \left( {\frac{1}{{1 - p}}} \right)\)

\(p = \frac{n}{m}\)

where p is load factor.

Calculation:

\(\frac{1}{{1 - p}} = 5\)

1 = 5 – 5p 

5p = 4

\(p = \frac{4}{5}\)

\(\frac{1}{p}\ln \left( {\frac{1}{{1 - p}}} \right) = \frac{5}{4}\ln \left( {\frac{1}{{1 - \frac{4}{5}\;}}} \right) = \frac{5}{4}\ln \left( 5 \right) = \frac{5}{4} \times 1.609 = 2.011\)

So, number of probes in successful search is 2.01

Answer: 1.5

Explanation:

In a hash-table with chaining and uniform hashing, the expected number of comparisons in an unsuccessful search is given by

α, where α is the load factor

\(\alpha = \frac{m}{n} = \frac{{60}}{{40}} = 1.5\)

Here, So, expected

number of comparisons for an unsuccessful search = 1.5

Worst case of the given problem is when a single 0 is followed by all 1’s i.e.

0111111111111……

Also, worst case can also be considered as when all 0’s are followed by single 1.

000000000………………1

Since, in both the cases there is a sorted sequence of 0 and 1 and for sorted sequence binary search is preferred.

At each stage, \(\frac{{low + high}}{2}\) element index is compared and if it is 1, search towards left and if it is 0 search towards right.

The correct answer is option 2.

Concept:

Hashing:

Hashing is the process of employing an algorithm to turn any length of input into a fixed-size string or integer. The principle behind hashing is to utilize a hash function to transform a given key to a smaller integer, which is then used as an index in a hash table.

A simple hash function that works with numeric values is known as the remainder method. It takes an element from a list and divides it by the size of the hash table. The remainder so generated is called the hash value.

h(element) = element % size(hash table)

Explanation:

The given data,

list of numbers (34, 16, 2, 93, 80, 77, 51) and has a table size is 10. 

The hash table is,

The remaining index stores the null values.

Hence the correct answer is 80, 51, 2, 93, 34, null, 16, 77, null, null.

The correct option is Search by Hashing.

CONCEPT:

In linear search, every element of a given list is compared one by one with the given key without skipping any element.

It is useful when we need to search for an item in a small unsorted list, but the time taken to search the list increases as the size of the list increases.

For example, consider a list of length 5 and the key element is present at the end of this list. Number of comparisons required to search the key element = size of list i.e 5

If we increase the size of the same list (say 15) and the key element is present at the end of this list. Number of comparisons required to search the key element = size of list i.e 15

In binary search, the key to be searched is compared with the middle element of a sorted list, If the element at the middle position:

i)  Matches the key the search is successful

ii) Is greater than the key then the key element may be present in the left part of the list

iii) Is smaller than the key, then the key element may be present in the right part of the list

This process continues till the element is found or the list is traversed completely.

Thus the time taken to search the list increases as the size of the list increases. But it will not be as large as the time required by linear search

Hash-based searching requires only one key comparison to find the position of a key, provided every element is present at its designated position decided by a hash function. 

For example, consider a list of length 5 and the hash function: h(element) = element % size(list)

A hashing function is a mathematical function that generates unique results for each unique value supplied to the hash function in constant time.

For example: Consider a list of length 5 and if we want to search for key = 12, the index returned by the hash function is h(12) = 12 % 5  = 2  and requires only one key comparison to find the key at that index

Similarly increasing the size of the list (say 15) and if we want to search for key = 12, the index returned by the hash function is h(12) = 12 % 5  = 12  and requires only one key comparison to find the key at that index

Thus it is independent of the length of the list.