Linear Search Iterative – Data Structure Questions and Answers

Data Structures & Algorithms Computer Science & Engineering

This set of Data Structure Multiple Choice Questions & Answers (MCQs) focuses on “Linear Search Iterative”.

1. What is the best case and worst case complexity of ordered linear search?
A) O(nlogn), O(logn)
B) O(logn), O(nlogn)
C) O(n), O(1)
D) O(1), O(n)

Explanation: Where the element is not present in the array, ordered linear search is better than unordered, but the best and worst cases remain the same, with the key element being located in the first or last place.

2. Choose the code snippet which uses recursion for linear search.
A)

public void linSearch(int[] arr, int first, int last, int key)
{
	if(first == last)
        {
		System.out.print("-1");
	}
	else
        {
		if(arr[first] == key)
                {
			System.out.print(first);
		}
		else
                {
			linSearch(arr, first+1, last, key);
		}
	}
}

B)

      public void linSearch(int[] arr, int first, int last, int key)
      {
		if(first == last)
                {
			System.out.print("-1");
		}
		else
                {
			if(arr[first] == key)
                        {
				System.out.print(first);
			}
			else
                        {
				linSearch(arr, first+1, last-1, key);
			}
		}
      }

C)

public void linSearch(int[] arr, int first, int last, int key)
{
	if(first == last)
        {
		System.out.print("-1");
	}
	else
        {
		if(arr[first] == key)
                {
			System.out.print(last);
		}
		else
                {
			linSearch(arr, first+1, last, key);
		}
	}
}

D)

public void linSearch(int[] arr, int first, int last, int key)
{
	if(first == last)
        {
		System.out.print("-1");
	}
	else
        {
		if(arr[first] == key)
                {
			System.out.print(first);
		}
		else
                {
			linSearch(arr, first+1, last+1, key);
		}
	}
}


Explanation: If the key and the array value at the first index are not equal, call the function again with the first index incremented.

3. What does the following piece of code do?

for (int i = 0; i < arr.length-1; i++)
{
    for (int j = i+1; j < arr.length; j++)
    {
        if( (arr[i].equals(arr[j])) && (i != j) )
        {
            System.out.println(arr[i]);
        }
    }
}

A) Print the duplicate elements in the array
B) Print the element with maximum frequency
C) Print the unique elements in the array
D) Prints the element with minimum frequnecy

Explanation: When the objects are identical but their indices are not, the print statement is executed.

4. Select the code snippet which prints the element with maximum frequency.
A)

public int findPopular(int[] a) 
{
	if (a == null || a.length == 0)
		return 0;
	Arrays.sort(a);
	int previous = a[0];
	int popular = a[0];
	int count = 1;
	int maxCount = 1;
	for (int i = 1; i < a.length; i++)
        {
		if (a[i] == previous)
		count++;
		else 
                {
			if (count > maxCount) 
                        {
				popular = a[i-1];
				maxCount = count;
			}
		previous = a[i];
		count = 1;
		}
	}
	return count > maxCount ? a[a.length-1] : popular;
}

B)

public int findPopular(int[] a) 
{
	if (a == null || a.length == 0)
		return 0;
	Arrays.sort(a);
	int previous = a[0];
	int popular = a[0];
	int count = 1;
	int maxCount = 1;
	for (int i = 1; i < a.length; i++) 
        {
		if (a[i] == previous)
			count++;
		else 
                {
			if (count > maxCount) 
                        {
				popular = a[i];
				maxCount = count;
			}
			previous = a[i];
			count = 1;
		}
	}
	return count > maxCount ? a[a.length-1] : popular;
}

C)

public int findPopular(int[] a) 
{
	if (a == null || a.length == 0)
		return 0;
	Arrays.sort(a);
	int previous = a[0];
	int popular = a[0];
	int count = 1;
	int maxCount = 1;
	for (int i = 1; i < a.length; i++) 
        {
		if (a[i+1] == previous)
			count++;
		else 
                {
			if (count > maxCount) 
                        {
				popular = a[i-1];
				maxCount = count;
			}
			previous = a[i];
			count = 1;
		}
	}
	return count > maxCount ? a[a.length-1] : popular;
}

D)

public int findPopular(int[] a) 
{
	if (a == null || a.length == 0)
		return 0;
	Arrays.sort(a);
	int previous = a[0];
	int popular = a[0];
	int count = 1;
	int maxCount = 1;
	for (int i = 1; i < a.length; i++) 
        {
		if (a[i+2] == previous)
			count++;
		else 
                {
			if (count > maxCount) 
                        {
				popular = a[i-1];
				maxCount = count;
			}
			previous = a[i];
			count = 1;
		}
	}
	return count > maxCount ? a[a.length-1] : popular;
}


Explanation: Traverse through the array to see if each element is equal to the previous one; since the array is sorted, this procedure has an O(nlogn) time complexity; if the array is not sorted, a Brute force strategy must be used, which has an O(nlogn) time complexity (n2).

5. Which of the following is a disadvantage of linear search?
A) Requires more space
B) Greater time complexities compared to other searching algorithms
C) Not easy to understand
D) Not easy to implement


Explanation: The complexity of linear search is O(n), which is much higher than the complexity of other searching strategies such as binary search (O(logn)). Other scanning methods are more difficult to execute and understand than linear search.

6. Where is linear searching used?
A) When the list has only a few elements
B) When performing a single search in an unordered list
C) Used all the time
D) When the list has only a few elements and When performing a single search in an unordered list

Explanation: When the list contains just a few elements and when conducting a single search in an unordered list, linear search is practical; however, when the list has more elements, the difficulty increases, and it is better to filter the list and use binary search or hashing.

7. Select the code snippet which performs unordered linear search iteratively?
A)

int unorderedLinearSearch(int arr[], int size, int data)
{
    int index;
    for(int i = 0; i < size; i++)
    {
        if(arr[i] == data)
        {
            index = i;
            break;
        }
    }
    return index;
}

B)

int unorderedLinearSearch(int arr[], int size, int data)
{
    int index;
    for(int i = 0; i < size; i++)
    {
        if(arr[i] == data)
        {
            break;
        }
    }
    return index;
}

C)

int unorderedLinearSearch(int arr[], int size, int data)
{
    int index;
    for(int i = 0; i <= size; i++)
    {
        if(arr[i] == data)
        {
            index = i;
            break;
        }
    }
    return index;
}

D)advertisementhttps://43a2f8f4cf44a4ed2ccdf1ce7eec6cf1.safeframe.googlesyndication.com/safeframe/1-0-38/html/container.html

int unorderedLinearSearch(int arr[], int size, int data)
{
    int index;
    for(int i = 0; i < size-1; i++)
    {
        if(arr[i] == data)
        {
            index = i;
            break;
        }
    }
    return index;
}


Explanation: The term “unordered” refers to an array in which the elements are not required to be ordered. To find an element in such an array, we must loop through all of the elements before we find the one we want.

8. What is the best case for linear search?
A) O(nlogn)
B) O(logn)
C) O(n)
D) O(1)

Explanation: Because the element is at the beginning of the array, O (1).

9. What is the worst case for linear search?
A) O(nlogn)
B) O(logn)
C) O(n)
D) O(1)

Explanation: The worst-case scenario is when the desired element is at the end of the array or not present at all; in this case, you must traverse to the end of the array, resulting in an O complexity (n).

10. Select the code snippet which performs ordered linear search iteratively?
A)

public int linearSearch(int arr[],int key,int size) 
{
       int index = -1;
	   int i = 0;
       while(size > 0) 
       {
             if(data[i] == key) 
             {
		  index = i;
             }
             if(data[i] > key)) 
             {
		 index = i;
                 break;
             }
             i++;
       }
       return index;
}

B)

public int linearSearch(int arr[],int key,int size) 
{
       int index = -1;
	   int i = 0;
       while(size > 0) 
       {
             if(data[i] == key) 
             {
		  index = i;
             }
             if(data[i] > key)) 
             {
                  break;
             }
             i++;
       }
       return index;
}

C)

public int linearSearch(int arr[],int key,int size) 
{
       int index = -1;
	   int i = 0;
       while(size > 0) 
       {
             if(data[i] == key) 
             {
		break;
             }
             if(data[i] > key)) 
             {
                 index = i;
             }
             i++;
        }
        return index;
}

D)

public int linearSearch(int arr[],int key,int size) 
{
       int index = -1;
	   int i = 0;
       while(size > 0) 
       {
             if(data[i] == key) 
             {
		break;
             }
             if(data[i] > key)) 
             {
                 break;
                 index=i; 
             }
             i++;
        }
        return index;
}


Explanation: The term ordered refers to the sorting of the array’s objects (here we assume ascending order). So, traverse the array until you find the element; if the value at I exceeds the key value at any point, the element isn’t in the array. This has a small advantage over unordered linear search in terms of performance.

The most basic type of search algorithm is a linear search. A Linear Search looks for a matching value in your list (or data structure) in a sequential manner. In other words, it scans a list one object at a time, rather than moving from one to the next. Consider it a method of navigating a phone book. A linear search, also known as a sequential search, is a method for locating an element within a list in computer science. It tests each element of the list one by one until a match is found or the entire list is searched. With each iteration, binary search algorithms usually halve the number of items to scan, allowing them to locate the given item (or determine its absence) in logarithmic time.

Leave a Reply

Your email address will not be published. Required fields are marked *