Computer Science Test - 13

Concept:

• A linear search or sequential search is a method for finding an element within an array or linked list or any data structure.
• It sequentially checks each element of the list until a match is found or the whole list has been searched.

Explanation:

int A[ ] = {2, 1, 4, 5 , 6, 7}

Array name: A

Search: 2

In first comparison, 2 is found

Best case time complexity is O(1)

The correct option is 4

CONCEPT:

It is a searching technique where every element of a given list is compared one by one with the given key.

This process repeats until the element matching with the key is found and we declare that the search is successful.

If no element matches the key is found and we have traversed the entire list, we declare the search is unsuccessful.

Pseudocode of linear search algorithm

procedure linear_search (list, key)

   for each item in the list

      if (item == key)

         return the item's index

      end if

   end for

end procedure

In the above question 

List     [ 7 , 3 , 9 , 15 , -6 , 11 ]

index    0   1   2    3     4     5   

We will match every element of the list with the given key=15 and we find element 15 at index 3 after performing 4 comparisons.

Answer: Option 2

Explanation:

Searching means finding whether a particular value is present in an array or not. If the value is present in the array, then the search is said to be successful and the searching process gives the location of that value in the array. However, if the value is not present in the array, the searching process displays an appropriate message and in this case, searching is said to be unsuccessful.

The correct option is Linear Search

CONCEPT:

Consider a given sorted list =[2,4,6,8,10 ] where key=2 which is present at the first index 

In linear search, every element of a given list is compared one by one with the given key.

We will match every element of the list with the given key=2 and we find element 2 at index 0 after performing 1 comparison.

Whereas, In binary search, the key to be searched is compared with the middle element of a sorted list:

i) If the element at the middle position matches the key the search is successful

ii) If the element at the middle position is greater than the key then the key element may be present in the left part of the list

iii) If the element at the middle position is smaller than the key, then the key element may be present in the right part of the list

This process continues till the element is found or the list is traversed completely.

In binary search, the number of comparisons required is 2.

Thus Number of Comparisons required by linear search is less than binary search.

The correct option is Given a list with sorted elements.

CONCEPT:

Binary search is a searching technique that makes use of the ordering of elements in the list to search a key quickly.

The key to be searched is compared with the element in the middle of a sorted list, this could result in any of the three possibilities:

i) If the element at the middle position matches the key the search is successful

ii) If the element at the middle position is greater than the key then the key element may be present in the left part of the list

iii) If the element at the middle position is smaller than the key, then the key element may be present in the right part of the list

This process continues till the element is found or the list is traversed completely.

Thus to use binary search the given list must be sorted.

The correct option is (1)

Concept:-

A simple approach is to do a linear search, i.e.

• Start from the leftmost element of arr[ ] and one by one compare X with each element of arr[ ]
• If X matches with an element, return the index
• If X does not match with any of the elements, return -1.

For example,

L=[2, 83, 63, 23, 96, 55, 12, 34, 24, 44]

X = 12

Element 12 is present at index 7,

Additional InformationLinear search:- Linear search is a sequential searching strategy in which we start at one end of the list and check each element until we find the target element. It is the most basic search algorithm.

Binary search:- A binary search is a search that finds the middle element is matched with a searched element.

Correct option is first = mid + 1 ,  last = mid - 1

CONCEPT:

Binary search is a searching technique that makes use of the ordering of elements in the list to search a key quickly.

The key to be searched is compared with the element in the middle of a sorted list, this could result in any of the three possibilities.

If the element at the middle position:

1.  matches the key. Thus the search is successful
2.  is smaller than the key, then the key element may be present in the right part of the list. Thus first=mid +1, to search the right half part only.
3.  is greater than the key, then the key element may be present in the left part of the list. Thus last=mid -1, to search the left half part only.

This splitting and reduction in list size continue till the key is found or the remaining list consists of only one item.

Searching is the process of finding an item with specified properties from a collection of items.

Types of searching:

1. Linear searching/Sequential searching

2. BinarySearch

Linear search or sequential search is a method for finding an element within a list.

It sequentially checks each element of the list until a match is found or the whole list has been searched.

The correct option is None of the above.

CONCEPT:

Binary search is a searching technique that makes use of the ordering of elements in the list to search a key quickly.

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

If the element at the middle position:

1.  matches the key. Thus the search is successful
2.  is smaller than the key, then the key element may be present in the right part of the list. Thus first=mid +1, to search the right half part only.
3.  is greater than the key, then the key element may be present in the left part of the list. Thus last=mid -1, to search the left half part only.

In the above question, the given list  L=[7,3,9,15,-6,11] is unordered/unsorted thus binary search cannot be applied to the given list.

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