Easy Interview Questions for Freshers on Binary Search Set 1

Easy Interview Questions for Freshers on Binary Search. These questions have beem asked in interviews for MNCs like Wipro, TCS and Infosys. This is subjective type short answers question and answer set no. 1 in this series.

Last Reviewed and Updated on February 7, 2020
Posted by Parveen(Hoven),
Aptitude Trainer and Software Developer

Interview and Exam Questions and Answers

This set contains a list of commonly asked questions. They are short interview questions aimed at freshers interview, campus placement drives, and also for job interviews. You can use these to have a quick grasp and brush-up of your fundamentals. These questions can be viewed on a mobile phone also because this website is built on responsive web design.

What is Modular Method?

In this method, modulus operation is applied on each key. This involves dividing the key value by the size of the hash table to obtain the remainder of the division. The remainder is considered as the address of the record corresponding to the key value.

What do you understand by folding method?

In this method, an address is calculated by breaking the keys into parts and then adding them. Consider the following keys:


4766934,5656975,4685637,3547807,7569664

Keys Dividing the keys Result
4766934 47+6634+4 6744
5656975 56+5697+5 5758
4685637 46+8563+7 8616
3547807 35+4780+7 4822
7569664 75+6966+4 7045

Now, truncate the result up to the digit based on the sizeof the hash table.Suppose the size of the table is 1000. Therfore, the hash address will be from 0 to 999. In the given example the result consists of four digits. Therefore, truncate the first digit of the result to obtain the address, as shown in fig below:

Keys Address
47669334 744
5656975 758
4685637 616
3547807 822
7569664 045

Write algorithm for binary search for a desired element.

The following algorithm is used for binary search:

  1. Accept the element to be searched
  2. Set lowerbound=0
  3. Set upperbound=n-1
  4. Set mid=(lowerbound+upperbound)/2
  5. If arr[mid]=desired element:
    1. Display "Found"
    2. Go to step 10
  6. If desired element<arr[mid]:
    1. Set upperbound=mid-1
  7. If desired element>arr[mid]:
    1. Set lowerbound=mid+1
  8. If lowerbound ≤upperbound:
    1. Go to step 4
  9. Display "Not Found"
  10. Exit

How do you define binary search?

A binary search or half-interval search finds the position of a specified value (the input "key") within a sorted array. Binary search is applied only on the list which is sorted and if the list to be searched is not sorted, it needs to be sorted before binary search can be applied to it.

Binary searches can be done on an array[Yes/No]?

Yes.

What is truncation method?

This method is used to compute the address of a record. In this method, a part of the numeric key is considered as an offset address of the corresponding record.

Which are the two principle criteria for selecting a hash function?

Two principle criteria for selecting a hash function are:

  1. It should be easy and quick to compute.
  2. It should achieve a uniform distribution of keys in address space.

What is the best case efficiency of binary search?

The best case efficiency of binary search is O(1).

How do you define hashing?

Hashing is the method of finding and retrieving information associated with a unique identifying key.

What is the worst case performance of binary search?

The worst case performance of binary search is O(log n).

My C/C++ Videos on Youtube

Here is the complete playlist for video lectures and tutorials for the absolute beginners. The language has been kept simple so that anybody can easily understand them. I have avoided complex jargon in these videos.