Linear Search & Binary Search - Computer Science Engineering (CSE) MCQ

# Linear Search & Binary Search - Computer Science Engineering (CSE) MCQ

Test Description

## 10 Questions MCQ Test GATE Computer Science Engineering(CSE) 2025 Mock Test Series - Linear Search & Binary Search

Linear Search & Binary Search for Computer Science Engineering (CSE) 2024 is part of GATE Computer Science Engineering(CSE) 2025 Mock Test Series preparation. The Linear Search & Binary Search questions and answers have been prepared according to the Computer Science Engineering (CSE) exam syllabus.The Linear Search & Binary Search MCQs are made for Computer Science Engineering (CSE) 2024 Exam. Find important definitions, questions, notes, meanings, examples, exercises, MCQs and online tests for Linear Search & Binary Search below.
Solutions of Linear Search & Binary Search questions in English are available as part of our GATE Computer Science Engineering(CSE) 2025 Mock Test Series for Computer Science Engineering (CSE) & Linear Search & Binary Search solutions in Hindi for GATE Computer Science Engineering(CSE) 2025 Mock Test Series course. Download more important topics, notes, lectures and mock test series for Computer Science Engineering (CSE) Exam by signing up for free. Attempt Linear Search & Binary Search | 10 questions in 30 minutes | Mock test for Computer Science Engineering (CSE) preparation | Free important questions MCQ to study GATE Computer Science Engineering(CSE) 2025 Mock Test Series for Computer Science Engineering (CSE) Exam | Download free PDF with solutions
Linear Search & Binary Search - Question 1

### What is the space complexity of the following binary search algorithm? int BinSearch(int a[], int n, int data) { int low = 0; int high = n-1; while (low <= high) { mid = low + (high-low)/2; if(a[mid] == data) return mid; else if(a[mid] < data) low = mid + 1; else high = mid - 1; } return -1; }

Detailed Solution for Linear Search & Binary Search - Question 1

Binary search is also called a half-interval search. It compares the required value with a middle element.
Generally, space complexity is the extra space that we are needed in the algorithm.
In a binary search, we have just a comparison between the array element and data element to be searched.
Since no extra space is needed: Space complexity: O(1)
Important Points:
In space complexity, an array that contains the original data is not included because it is already given and we have not added any extra space apart from that.
The time complexity of binary search: O(log n)

Linear Search & Binary Search - Question 2

### Choose true statement : (I) Binary search is faster than linear search. (II) Binary search may not be applied on all the input lists on which linear search can be applied.

Detailed Solution for Linear Search & Binary Search - Question 2

The correct answer is option C.
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.

 1 Crore+ students have signed up on EduRev. Have you?
Linear Search & Binary Search - Question 3

### For which of the following tasks, stack is not suitable data structure? (a) Binary search in an array (b) Breadth first search (c) Implementing function calls (d) Process scheduling

Detailed Solution for Linear Search & Binary Search - Question 3

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.

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.

Linear Search & Binary Search - Question 4

The minimum number of comparisons for a particular record among 32 sorted records through binary search method will be:

Detailed Solution for Linear Search & Binary Search - Question 4

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(log2n)
Here, we have to apply the binary search on 32 elements. So, it will take log232 = 5 comparisons to search for the element.

Linear Search & Binary Search - Question 5

What is the worst-case number of arithmetic operations performed by recursive binary search on a sorted array of size n?

Detailed Solution for Linear Search & Binary Search - Question 5

The correct answer is option 3:
Key Points

• Binary search has the Worst-case and avg case time complexity O(log2n) and best case O(1) in an array. So, it is can also be written as θ(log2n) and θ (1).
• No of arithmetic operations will be θ (logn) in the worst case as every comparison needs 2 operations + and / by 2.
Linear Search & Binary Search - Question 6

Consider the following array A, and the searching element is X. How many comparisons are required to search an element X in array A.
A[ ]= {25, 45, 87, 21, 18, 49, 13, 115, 83, 65}
X = 83

Detailed Solution for Linear Search & Binary Search - Question 6

The correct answer is option C.
Concept:
Linear search is a sequential searching strategy in which we start at one end of the list and examine each member until we find the target element. It is the most basic search algorithm.
The given data is,
A[ ]= {25, 45, 87, 21, 18, 49, 13, 115, 83, 65}
X = 83

Explanation:
Compare element 25 with 83.
Hence the search is not successful and continues the program.
Compare element 45 with 83.
Hence the search is not successful and continues the program.
Compare element 87 with 83.
Hence the search is not successful and continues the program.
Compare element 21 with 83.
Hence the search is not successful and continues the program.
Compare element 18 with 83.
Hence the search is not successful and continues the program.
Compare element 49 with 83.
Hence the search is not successful and continues the program.
Compare element 13 with 83.
Hence the search is not successful and continues the program.
Compare element 115 with 83.
Hence the search is not successful and continues the program.
Compare element 83 with 83.
Hence the search is successful and exits the program.
Total comparsions are=9.
Hence the correct answer is 9.

Linear Search & Binary Search - Question 7

Which of the following is/are true about the search in an array data structure with N element?
I. linear search is also called random search
II. At worst case, the number of comparisons needed in linear search is N

Detailed Solution for Linear Search & Binary Search - Question 7
• If an element is a search in an array data structure in a sequence, then it is linear search or sometimes also called sequential search
• The worst-case in searching arises: If the element is not found or the element to search is the last element; The worst-case number of comparisons is N. Bacause in linear search the search is performed in a sequence from first to last element.
Linear Search & Binary Search - Question 8

Which of the following is/are true about the search in an array data structure with N element?
I. linear search is also called random search
II. At worst case, the number of comparisons needed in linear search is N

Detailed Solution for Linear Search & Binary Search - Question 8
• If an element is a search in an array data structure in a sequence, then it is linear search or sometimes also called sequential search
• The worst-case in searching arises: If the element is not found or the element to search is the last element; The worst-case number of comparisons is N. Bacause in linear search the search is performed in a sequence from first to last element.
Linear Search & Binary Search - Question 9

Consider the following array A, and the searching element is X. How many comparisons are required to search an element X in array A.
A[ ]= {25, 45, 87, 21, 18, 49, 13, 115, 83, 65}
X = 83

Detailed Solution for Linear Search & Binary Search - Question 9

The correct answer is option c.
Concept:
Linear search is a sequential searching strategy in which we start at one end of the list and examine each member until we find the target element. It is the most basic search algorithm.
The given data is,
A[ ]= {25, 45, 87, 21, 18, 49, 13, 115, 83, 65}
X = 83
Explanation:
Compare element 25 with 83.
Hence the search is not successful and continues the program.
Compare element 45 with 83.
Hence the search is not successful and continues the program.
Compare element 87 with 83.
Hence the search is not successful and continues the program.
Compare element 21 with 83.
Hence the search is not successful and continues the program.
Compare element 18 with 83.
Hence the search is not successful and continues the program.
Compare element 49 with 83.
Hence the search is not successful and continues the program.
Compare element 13 with 83.
Hence the search is not successful and continues the program.
Compare element 115 with 83.
Hence the search is not successful and continues the program.
Compare element 83 with 83.
Hence the search is successful and exits the program.
Total comparsions are=9.
Hence the correct answer is 9.

Linear Search & Binary Search - Question 10

In binary search, the key to be searched is compared with the element in the __________ of a sorted list.

Detailed Solution for Linear Search & Binary Search - Question 10

Concept:
The binary search algorithm is used to find a specific element in a sorted array. The target value is compared to the array's middle element in a binary search.

Key Points

• Sequential search is substantially less efficient than binary search. The elements must, however, be presorted before using the binary search method.
• It works by dividing the area of the list that could contain the item in half until the number of possible sites is reduced to just one.
• Binary search is an efficient algorithm and is better than linear search in terms of time complexity.
• Because it splits the array into two half as part of the process, it's called binary. A binary search will initially compare the item in the middle of the array to the search terms.
​​​​​​​

## GATE Computer Science Engineering(CSE) 2025 Mock Test Series

55 docs|215 tests
Information about Linear Search & Binary Search Page
In this test you can find the Exam questions for Linear Search & Binary Search solved & explained in the simplest way possible. Besides giving Questions and answers for Linear Search & Binary Search, EduRev gives you an ample number of Online tests for practice

## GATE Computer Science Engineering(CSE) 2025 Mock Test Series

55 docs|215 tests