Easy Interview Questions for Freshers on Binary Search Set 2

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

Give some examples where binary search could be used?

The examples of binary search are:

  1. Number guessing game
  2. Word lists
  3. Applications to complexity theory

What is the worst case complexity of binary search?

The worst case complexity of binary search is O(1).

Which is the fundamental principle of hashing?

The fundamental principle of hashing is to convert a given key value to an offset address to retrieve a record.

What is average case performance of binary search?

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

Give an example of modular method.

Consider the following keys:


36475611,47566933,75669353,34547579,46483499
Assume that the size of the table is 43,the addresses of the preceding keys will be calculated as:
36475611 mod 43=1
47566933 mod 43=32
75669353 mod 43=17
34547579 mod 43=3
46483499 mod 43=26

What are the various steps while performing Binary Search?

To perform binary search following steps are performed: Suppose in given list we have to search element 13

  1. Divide the list into two equal halves.To divide the list,you need to obtain the index of the middlemost element in the list.The index of the middlemost element is determine with the help of the following formula:
    Mid=(Lower bound+Upper bound)/2
    Here,lower bound(LB) is the index of the first element in the list and the Upper bound(UB) is the index of the last element in the list.
    In the given list,LB is 0 and UB is 8.

    Therefore,
    Mid=(LB+UB)/2
    Mid=(0+8)/2
    Mid=4
    After dividing the list,there can be three possible condition:
    1. Element to be searched=middle element:If this condition holds true,the desired element is found at arr[mid]
    2. Element to be searched<middle element:If this condition holds true,search the item towards the left of the middle element.
    3. Element to be searched>middle element:If this condition holds true,search the element towards the right of the middle element.
      In the given example,the middle element is at index 4,as shown in the following figure.
  2. The element at index 4 is 25,which is greater than 13.Therefore,search the element towards the left of the middle element,that is,in the lsit arr[0] to arr[3].Here LB is 0 and the UB is equal to mid-1,as shown in the following figure.
  3. Again divide the list into two halves by determining the value of Mid.
    Here,
    Mid=(LB+UB)/2
    Mid=(0+3)/2
    Mid=1
    Therefore,the middle element will be at index 1,as shown in the following figure.

    The element at index 1 is 13,which is the desired element.

Describe Mid Square Method with an example.

In this method, we square the key, and then take some digits from the middle of the number as an address of the corresponding key. Consider the given set of keys:


2636,5657,5869,4756,6079

Key (Keys)²
2636 6948496
5657 32001649
5869 34445161
4756 22619536
6079 36954241

Now, take the 4th and 5th digits from the square of each key. Then we can consider them as the address of the corresponding keys. Therefore, addresses of the given keys will be 84, 01, 45, 19 and 54.

List some techniques that are used to design a hash function?

There are various techniques that can be used to design the hash function:

  1. Truncation Method
  2. Modular Method
  3. Mid Square Method
  4. Folding Method

In binary search algorithm, after every search operation, the search gets reduced by ______?

In binary search algorithm, after every search operation, the search gets reduced by 1/4.

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.

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.