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

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) 

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.

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

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.

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.

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

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

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.

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