Which of the following is true about the binary search algorithm when applied to a sorted array?
Which of the following is true about the binary search algorithm when applied to a sorted array?
Show Hint
Binary search only works on sorted arrays. It divides the search space in half each time, making it an efficient O(log n) algorithm. Always ensure that the array is sorted before applying binary search.
It always has a time complexity of O(n)
It works on unsorted arrays
It divides the search space into two equal halves on each iteration
It requires that the array be sorted in descending order
The Correct Option is C
Solution and Explanation
Understanding Binary Search
- Binary search works by dividing the search space in half at each step.
- It requires the array to be sorted in ascending order for proper functioning.
Thus, the correct statement is: "It divides the search space into two equal halves on each iteration.
Top GATE CS Computer Organization and Architecture Questions
- Instruction format has the following structure.Instruction number OPCODE destination Source \(1\) and Source \(2\).
\(I_1:\) Div \(R_3 R_1 R_2;\)
\(I_2:\) Sub \(R_5 R_3 R_4;\)
\(I_3:\) Add \(R_3 R_5 R_6;\)
\(I_4:\) Mul \(R_7 R_3 R_8;\) - Consider a computer with a \(4 \, \text{MHz}\) processor. Its DMA controller can transfer \(8 \, \text{bytes}\) in \(1\) cycle from a device to main memory through cycle stealing at regular intervals. Which one of the following is the data transfer rate (in bits per second}) of the DMA controller if \(1\%\) of the processor cycles are used for DMA?
- The format of a single-precision floating-point number as per the IEEE 754 standard is:} \begin{center} \begin{tabular}{|c|c|c|} \hline Sign (1 bit) & Exponent (8 bits) & Mantissa (23 bits)
\hline \end{tabular} \end{center} Choose the largest floating-point number among the following options: - Let \( T(n) \) be the recurrence relation defined as follows: \[ T(0) = 1, \quad T(1) = 2, \quad T(n) = 5T(n-1) - 6T(n-2) \quad \text{for } n \geq 2 \] Which one of the following statements is TRUE?
- Node X has a TCP connection open to node Y. The packets from X to Y go through an intermediate IP router R. Ethernet switch S is the first switch on the network path between X and R. Consider a packet sent from X to Y over this connection. Which of the following statements is/are TRUE about the destination IP and MAC addresses on this packet at the time it leaves X?
Top GATE CS Memory hierarchy Questions
Given a pipeline with 5 stages, the delay for each stage is as follows:
\[ \begin{array}{|c|c|} \hline \textbf{Stage} & \textbf{Delay (ns)} \\ \hline 1 & 250 \\ 2 & 150 \\ 3 & 100 \\ 4 & 200 \\ 5 & 50 \\ \hline \end{array} \]The buffer delay is 10 ns. Find the time for \( n = 1000 \) instructions.
Consider the following operations on an initially empty stack:
Push 10
Push 20
Pop
Push 30
Pop
Push 40
What is the final content of the stack?A disk of size 512M bytes is divided into blocks of 64K bytes. A file is stored in the disk using linked allocation. In linked allocation, each data block reserves 4 bytes to store the pointer to the next data block. The link part of the last data block contains a NULL pointer (also of 4 bytes). Suppose a file of 1M bytes needs to be stored in the disk. Assume, 1K = \(2^{10}\) and 1M = \(2^{20}\). The amount of space in bytes that will be wasted due to internal fragmentation is ___________. (Answer in integer)
Refer to the given 3-address code sequence. This code sequence is split into basic blocks. The number of basic blocks is __________. (Answer in integer)
1001: i = 1
1002: j = 1
1003: t1 = 10i
1004: t2 = t1+j
1005: t3 = 8t2
1006: t4 = t3-88
1007: a[t4] = 0.0
1008: j = j+1
1009: if j <= 10 goto 1003
1010: i = i+1
1011: if i <= 10 goto 1002
1012: i = 1
1013: t5 = i-1
1014: t6 = 88t5
1015: a[t6] = 1.0
1016: i = i+1
1017: if i <= 10 goto 1013A computer has a memory hierarchy consisting of two-level cache (L1 and L2) and a main memory. If the processor needs to access data from memory, it first looks into L1 cache. If the data is not found in L1 cache, it goes to L2 cache. If it fails to get the data from L2 cache, it goes to main memory, where the data is definitely available. Hit rates and access times of various memory units are shown in the figure. The average memory access time in nanoseconds (ns) is __________. (rounded off to two decimal places)
Top GATE CS Questions
- Which of the following sequences when stored in an array at locations A[1],..., A[10] forms a max-heap?
- The Lucas sequence Ln is defined by the recurrence relation: Ln = Ln−1 + Ln−2, for n ≥ 3, with L1 = 1 and L2 = 3. Which one of the options given is TRUE?
- Which of the following fields of IP header is/are always modified by any router before it forwards to IP Packet ?
- Which one of the following CIDR profix exactly represent the range of IP addresses 10.12.2.0 to 10.12.3.255?
- Consider an ethernet segment whose transmission is \(10^8\) bits per second. Maximum segment length \(500\ m\), speed of the provocation media velocity is \(2 × 10^8\) meter per second. What is the minimum frame size in bits ?