Top MCQs on Searching Algorithm with Answers

Consider the following program that attempts to locate an element x in a sorted array a[ ] using binary search. Assume N>1. The program is erroneous. Under what conditions does the program fail?

#include <iostream> #include <vector> using namespace std; int find(vector<int>a, int n) {  int i = 1, j = n;  int x;  do {  int k = (i + j) / 2;  if (a[k] < x) i = k + 1;  else j = k;  } while (a[k] != x && i < j);    if (a[k] == x)  cout << "x is in the array" << endl;  else  cout << "x is not in the array" << endl;  return 0; } 

#include <stdio.h> #include <stdbool.h> int find(int a[], int n, int x) {  int i = 1, j = n;  int k;  do {  k = (i + j) / 2;  if (a[k] < x) i = k + 1;  else j = k;  } while (a[k] != x && i < j);    if (a[k] == x)  printf("x is in the array\n");  else  printf("x is not in the array\n");  return 0; } 

import java.util.List; public class Main {  public static void find(int arr[], int n, int x) {  int i = 0, j = n;  int k;  do {  k = (i + j) / 2;  if (arr[k] < x) i = k + 1;  else j = k;  } while (i < j && arr[k] != x);  if (arr[k] == x)  System.out.println("x is in the array");  else  System.out.println("x is not in the array");  } } 

def find(a, n, x): i = 0 j = n while i < j: k = (i + j) // 2 if a[k] < x: i = k + 1 else: j = k if i < len(a) and a[i] == x: print("x is in the array") else: print("x is not in the array") 

function find(a, n, x) {  let i = 0, j = n;  let k;  do {  k = Math.floor((i + j) / 2);  if (a[k] < x) i = k + 1;  else j = k;  } while (a[k] !== x && i < j);    if (a[k] === x)  console.log("x is in the array");  else  console.log("x is not in the array"); } 

Linear search is also called------

Given a sorted array of integers, what can be the minimum worst-case time complexity to find ceiling of a number x in given array? The ceiling of an element x is the smallest element present in array which is greater than or equal to x. Ceiling is not present if x is greater than the maximum element present in array. For example, if the given array is {12, 67, 90, 100, 300, 399} and x = 95, then the output should be 100.

The increasing order of performance  of the searching algorithms are:

The average case occurs in the Linear Search Algorithm when:

Consider the function given below. Assume that the array listA contains n (> 0) elements, sorted in ascending order. 

#include <vector> using namespace std; int ProcessArray(vector<int>& listA, int x, int n) {  int i = 0;  int j = n - 1;  while (i <= j) {  int k = (i + j) / 2;  if (x <= listA[k]) {  j = k - 1;  }  if (listA[k] <= x) {  i = k + 1;  }  }  if (listA[k] == x) {  return k;  } else {  return -1;  } } 

#include <stdio.h> 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; } 

public class Main {  public static int ProcessArray(int[] listA, int x, int n) {  int i = 0, j = n - 1, k;  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;  } } 

def ProcessArray(listA, x, n): i = 0 j = n - 1 while i <= j: k = (i + j) // 2 if x <= listA[k]: j = k - 1 if listA[k] <= x: i = k + 1 if listA[k] == x: return k else: return -1 

function ProcessArray(listA, x, n) {  let i = 0;  let j = n - 1;  let k;  do {  k = Math.floor((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?

The average number of key comparisons done in a successful sequential search in a list of length n is

The necessary condition for using binary search in an array is :-

what is the name of the below searching Algorithm?

int function(vector<int> arr,int x){ int n = arr.size();  if(n == 0) return -1; // Find range for binary search by repeatedly doubling i int i = 1; while(i < n and arr[i] < x) i *= 2; // Perform binary search on the range [i/2, min(i, n-1)] int left = i /2; int right = min(i, n-1); while(left <= right){ int mid = (left + right)/2;  if(arr[mid] == x) return mid; else if(arr[mid] < x) left = mid + 1; else right = mid - 1; } return -1; } 

#include <stdio.h> #include <stddef.h> int binary_search(int arr[], int n, int x) {  if(n == 0)  return -1;  // Find range for binary search by repeatedly doubling i  int i = 1;  while(i < n && arr[i] < x)  i *= 2;  // Perform binary search on the range [i/2, min(i, n-1)]  int left = i / 2;  int right = (i < n) ? i : n - 1;  while(left <= right) {  int mid = (left + right) / 2;    if(arr[mid] == x) return mid;  else if(arr[mid] < x) left = mid + 1;  else right = mid - 1;  }  return -1; } 

import java.util.*; public class Main {  public static int function(List<Integer> arr, int x) {  int n = arr.size();    if (n == 0)  return -1;  // Find range for binary search by repeatedly doubling i  int i = 1;  while (i < n && arr.get(i) < x)  i *= 2;  // Perform binary search on the range [i/2, min(i, n-1)]  int left = i / 2;  int right = Math.min(i, n - 1);  while (left <= right) {  int mid = (left + right) / 2;  if (arr.get(mid) == x) return mid;  else if (arr.get(mid) < x) left = mid + 1;  else right = mid - 1;  }  return -1;  } } 

def function(arr, x): n = len(arr) if n == 0: return -1 # Find range for binary search by repeatedly doubling i i = 1 while i < n and arr[i] < x: i *= 2 # Perform binary search on the range [i/2, min(i, n-1)] left = i // 2 right = min(i, n - 1) while left <= right: mid = (left + right) // 2 if arr[mid] == x: return mid elif arr[mid] < x: left = mid + 1 else: right = mid - 1 return -1 

function functionSearch(arr, x) {  let n = arr.length;    if (n === 0)  return -1;  // Find range for binary search by repeatedly doubling i  let i = 1;  while (i < n && arr[i] < x)  i *= 2;  // Perform binary search on the range [i/2, Math.min(i, n-1)]  let left = Math.floor(i / 2);  let right = Math.min(i, n - 1);  while (left <= right) {  let mid = Math.floor((left + right) / 2);  if (arr[mid] === x) return mid;  else if (arr[mid] < x) left = mid + 1;  else right = mid - 1;  }  return -1; } 

What is the time complexity for performing Jump search?