Question

Assume that the incoming array is sorted and adjust the algorithm below to allow for faster exit if the searched for value is not in the list.

void linearsearch (int n, int Arr[], int a, int& index){

index = 1;

while (index <= n && Arr[index] != a)

index++;

if (index > n)

index = 0;

}

Answer 1

In the algorithm mentioned, the assumptions made are

n = number of elements in the Array

Arr[] = Sorted array provided

a = element to be searched

index = index element to be used in the algorithm

There could be many ways out of which I am suggesting two ways to exit out faster if the searched value is not in the list

1) Include a separate If condition after while loop

void linearsearch (int n, int Arr[], int a, int& index){

index = 1;

while (index <= n && Arr[index] != a)

/* Since the array is sorted.We can search the list further only if the element is larger than current Index value.If it is smaller and not matching value,then we will exit from loop .In this way search time will be reduced */

if (a > Arr[index])

index++;

else

print (“Element”,a, “not present in the searched array”)

exit; // Break from the loop displaying the above message

if (index > n)

index = 0;

}

2) Modify the while loop to add equality condition ( Arr[index] < a ) as well

void linearsearch (int n, int Arr[], int a, int& index){

index = 1;

/* Since the array is sorted.We can search the list further only if the element is larger than current Index value.We will add this extra condition in the While condition so as to exit the search loop If indexed value is greater than the searched value .In this way search time will be reduced */

while (index <= n && Arr[index] != a && Arr[index] < a)

if (index > n)

index = 0;

}