Exams › GATE › Technical

Consider the C function given below. Assume that the array listA contains n (> 0) elements, sorted in ascending order. int ProcessArray(int *listA, int x, int n) { int i, j, k; i = 0; j = n-1; do { k = (i+j)/2; if (x <= listA[k]) j = k-1; if (listA[k] <= x) i = k+1; }while (i <= j); if (listA[k] == x) return(k); else return -1; } Which one of the following statements about the function ProcessArray is CORRECT?

1. It will run into an infinite loop when x is not in listA.
2. It is an implementation of binary search.
3. It will always find the maximum element in listA.
4. It will return -1 even when x is present in listA.

Correct answer: It is an implementation of binary search.

Solution

The function uses a divide-and-conquer approach to efficiently search for the element x within the sorted array listA, which is characteristic of binary search. It repeatedly narrows down the search range by comparing x with the middle element until it either finds x or determines that it is not present.

Related GATE Technical questions

• Let G = (V,E) be a directed graph where V is the set of vertices and E the set of edges. Then which one of the following graphs has the same strongly connected components as G ?
• Consider the following program in C language: #include <stdio.h> main() { int i; int *pi = &i; scanf("%d", pi); printf("%d ", i+5); } Which one of the following statements is TRUE?
• Let G be a graph with n vertices and m edges. What is the tightest upper bound on the running time of Depth First Search on G, when G is represented as an adjacency matrix?
• Let P be a quicksort program to sort numbers in ascending order using the first element as the pivot. Let t1 and t2 be the number of comparisons made by P for the inputs [1 2 3 4 5] and [4 1 5 3 2] respectively. Which one of the following holds?
• Which one of the following is TRUE ?
• Match the following: 1) Waterfall model 2) Evolutionary model 3) Component-based software engineering 4) Spiral development a) Specifications can be developed incrementally b) Requirements compromises are inevitable c) Explicit recognition of risk d) Inflexible partitioning of the project into stages

⚔️ Practice GATE Technical free + battle 1v1 →