Binary MCQ Quiz - Objective Question with Answer for Binary - Download Free PDF

Concept :

Stack is a data structure in which elements can be inserted and deleted only from one end i.e. top of the stack. It follows the LIFO property i.e. last in first out.

Explanation:

(a) Binary search in an array

Binary search in an array can be performed with the help of stack.  Binary search works on the divide and conquer approach and finds the middle element and then perform the search in the left side if element is smaller than the middle element otherwise search proceed in the right of middle element.

(b) Breadth first search

Breadth first search is graph traversal algorithm. It uses queue data structure to traverse the graph or the tree. It is also used to find the connected components in a graph.

(c) Implementing function calls

Function calls are implemented using the stack data structure. As, when a function call arrives then the state or the data currently operated on is stored on the stack where it is resumed after the execution of function call.

(d) Process scheduling

Process scheduling is implemented using the queue data structure . Ready queue is maintained for the processes which are ready for the execution.

The correct answer is T(n) = T(n/2) O (1).

Key Points

• The binary search algorithm is a search algorithm that finds the position of a target value within a sorted array.
• Binary search works by repeatedly dividing the search interval in half.
• If the value of the search key is less than the item in the middle of the interval, narrow the interval to the lower half.
• Otherwise, narrow it to the upper half. Repeat until the value is found or the interval is empty.

Additional Information

• The recurrence relation for the binary search algorithm is T(n) = T(n/2) + O(1).
• This is because at each step, the algorithm divides the problem size by 2 (hence T(n/2)) and performs a constant amount of work (O(1)).
• The time complexity of binary search is O(log n) in the worst case.
• Binary search is more efficient than linear search, especially for large datasets.

The correct answer is 5

Explanation:

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, the element index is compared and if it is 1, search towards left and if it is 0 search towards the right.

Total worst-case number of probes performed by an optimal algorithm is = ⌈log2  31⌉ = 5 = 5

Example:

Optimal Algorithm: Binary search

Consider element containing 7 elements

Maximum probes = ⌈ log27 ⌉ = 3

For 31 elements

Maximum probes = ⌈ log2  31⌉ = 5

The order of the binary search algorithm is O(log n).

Key Points

• The binary search algorithm is an efficient algorithm for finding an item from a sorted list of items.
  • It works by repeatedly dividing in half the portion of the list that could contain the item, until you've narrowed down the possible locations to just one.
  • In each step, the algorithm compares the target value to the middle element of the list.
  • If the target value is less than the middle element, the search continues in the lower half of the list; otherwise, it continues in the upper half.
  • This process is repeated until the target value is found or the remaining list is empty.
  • Because the list is divided in half each time, the time complexity of binary search is O(log n).

Additional Information

• Binary search can only be applied to a list that is sorted. If the list is unsorted, it must be sorted first, which can take O(n log n) time.
• In contrast, linear search runs in O(n) time and does not require the list to be sorted.
• The binary search algorithm is commonly used in computer science, including in applications such as database indexing and algorithmic trading.
• In practical applications, binary search can significantly reduce the time required to search large datasets, making it a valuable tool for optimizing performance.

The idea of binary search is to use the information that the array is sorted and reduce the time complexity to O(Logn). We basically ignore half of the elements just after one comparison.

1) Compare x with the middle element.

2) If x matches with middle element, we return the mid index.

3) Else If x is greater than the mid element, then x can only lie in right half subarray after the mid element. So we recur for right half.

4) Else (x is smaller) recur for the left half.

The time complexity of Binary Search can be written as

Binary search algorithm:

Binary search algorithm is used to find an element in an already sorted array.

STEPS 1:

It finds the middle element of the array and compare the element with the element to be searched, if it matches then return true.

STEPS 2:

If not, then divide the array into two halves in which if element to be search is less than middle element then search takes place in left part otherwise search in right half.

STEP 3:

Repeat this process, until you get the element.

Explanation:

For worst case 52

Worst Case: Search 50 in below give array

\({\rm{midde\;index}} = \frac{{0 + 9}}{2} = 4\therefore {\rm{a}}\left[ 4 \right] = 35\)

50 > 32

\({\rm{midde\;index}} = \frac{{5 + 9}}{2} = 7\;\therefore {\rm{a}}\left[ 7 \right] = 63\)

50 < 63

\({\rm{midde\;index}} = \frac{{5 + 6}}{2} = 8\;\therefore {\rm{a}}\left[ 5 \right] = 50\)

matched

T(n) = O(log n)

Also, for average case:

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

Concept:

Statement 1: Binary search is faster than linear search.

True, Unless the array size is tiny, binary search is faster than linear search. However, sorting the array is required before doing a binary search. In contrast to binary search, there exist specialized data structures created for quick searching, such as hash tables.

Statement 2:Binary search may not be applied on all the input lists on which linear search can be applied.

True, Binary search is applied only on the sorted list it can not apply to an unsorted list. Whereas linear search is applicable for all types of lists. It means the sorted or unsorted type of lists.

Hence the correct answer is Both I and II.

The correct answer is option 3:

Key Points

• Binary search has the Worst-case and avg case time complexity O(log₂n) and best case O(1) in an array. So, it is can also be written as θ(log₂n)

and θ (1).

• No of arithmetic operations will be θ (logn) in the worst case as every comparison needs 2 operations + and / by 2.

Concept :

Stack is a data structure in which elements can be inserted and deleted only from one end i.e. top of the stack. It follows the LIFO property i.e. last in first out.

Explanation:

(a) Binary search in an array

Binary search in an array can be performed with the help of stack.  Binary search works on the divide and conquer approach and finds the middle element and then perform the search in the left side if element is smaller than the middle element otherwise search proceed in the right of middle element.

(b) Breadth first search

Breadth first search is graph traversal algorithm. It uses queue data structure to traverse the graph or the tree. It is also used to find the connected components in a graph.

(c) Implementing function calls

Function calls are implemented using the stack data structure. As, when a function call arrives then the state or the data currently operated on is stored on the stack where it is resumed after the execution of function call.

(d) Process scheduling

Process scheduling is implemented using the queue data structure . Ready queue is maintained for the processes which are ready for the execution.

Concept:

Binary search: Binary search follows the divide and conquer approach. To search for an element, first find the middle element, if a match found, then return the location. Otherwise, if the element is less than the middle element search will proceed in the left half, else the search will proceed into the right half.

Explanation:

Recurrence relation for binary search :

T(n) = T(n/2) + 1

Time Complexity of this algorithm: O(log₂n)

Here, we have to apply the binary search on 32 elements. So, it will take log₂32 = 5 comparisons to search for the element.

The correct answer is T(n) = T(n/2) O (1).

Key Points

• The binary search algorithm is a search algorithm that finds the position of a target value within a sorted array.
• Binary search works by repeatedly dividing the search interval in half.
• If the value of the search key is less than the item in the middle of the interval, narrow the interval to the lower half.
• Otherwise, narrow it to the upper half. Repeat until the value is found or the interval is empty.

Additional Information

• The recurrence relation for the binary search algorithm is T(n) = T(n/2) + O(1).
• This is because at each step, the algorithm divides the problem size by 2 (hence T(n/2)) and performs a constant amount of work (O(1)).
• The time complexity of binary search is O(log n) in the worst case.
• Binary search is more efficient than linear search, especially for large datasets.

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, the element index is compared and if it is 1, search towards left and if it is 0 search towards the right.

Total worst-case number of probes performed by an optimal algorithm = ⌈log2  63⌉ = 6

Example:

Optimal Algorithm: Binary search

Consider element containing 7 elements

Maximum probes = ⌈ log27 ⌉ = 3

For 31 elements

Maximum probes = ⌈ log2  63⌉ = 6

Binary search algorithm:

Binary search algorithm is used to find an element in an already sorted array.

STEPS 1:

It finds the middle element of the array and compare the element with the element to be searched, if it matches then return true.

STEPS 2:

If not, then divide the array into two halves in which if element to be search is less than middle element then search takes place in left part otherwise search in right half.

STEP 3:

Repeat this process, until you get the element.

Explanation:

For worst case 52

Worst Case: Search 50 in below give array

\({\rm{midde\;index}} = \frac{{0 + 9}}{2} = 4\therefore {\rm{a}}\left[ 4 \right] = 35\)

50 > 32

\({\rm{midde\;index}} = \frac{{5 + 9}}{2} = 7\;\therefore {\rm{a}}\left[ 7 \right] = 63\)

50 < 63

\({\rm{midde\;index}} = \frac{{5 + 6}}{2} = 8\;\therefore {\rm{a}}\left[ 5 \right] = 50\)

matched

T(n) = O(log n)

Also, for average case:

Concept:

Binary search works only on a sorted set of elements. Suppose we want to search for an element k in a sorted array. Then first find the middle element and compare that with k, if both are equal then return. Otherwise proceed search in left or right direction. If k is greater than middle element, search proceed in right direction, else in left direction.

Time complexity:

If there are n element in sorted array, then time complexity for binary search will be:

T(n) = T(n/2) + 1

T(n) = O (log₂n)

Example:

a[0]           a[1]          a[2]           a[3]           a[4]          a[5]          a[6]

Suppose we have to search for element 10

Here n (total elements) = 7

Middle element is = a[3] = 8

8 is not equal to 10,

10 > 8, search will proceed in right of a[3].

Now find the middle of a[4] to a[6] which is a[5] = 13

13 is also not matched with 10

Now 10 < 13, so search will take place between a[3] and a[5] i.e. a[4]

a[4] = 10 which is same as the element we are searching for. So, process ends here.