Question

C programming (you don't need to write program)

Problem 1 [Linear Search with Early Stop]

Below you will find a linear search function with early stop. A linear search is just a naive search - you go through each of the elements of a list one by one. Early stop works only on sorted list. Early stop means, instead of going through whole list, we will stop when your number to search can no longer be possibly found in the rest of the list. For instance, if my array a is sorted in ascending order, my linear search for a number x can stop when we reach an element a[i] > x.

Notice if no match is found, the convention for search functions is to return -1.

#include <stdio.h> // Linear search with early stop - just search one by one; // It assumes list is sorted in ASCENDING ORDER // this function returns index of item found, or -1 if no match is found int comparisonsUsed = 0; int linearSearch(int a[], int lastIndex, int x) {     // lastIndex is the last index of the array     // x is the number to search for in the array        int i = 0;     while (i <= lastIndex && a[i] <= x) {         comparisonsUsed++;         if (x == a[i]) return i;         i++;     }     return -1; } int main(void) {     int a[] = {0,1,4,5,6,7,9,11,12,15};     int size = 10;     int x = 10;     int foundIndex = linearSearch(a, size-1, x);     printf("Comparisons used: %d\n",comparisonsUsed);     if (foundIndex == -1)         printf("* Element x is not found in list\n");     else         printf("* Element x is found at index %d\n",foundIndex);     return 0; }

You will notice that I am tracking the number of comparisons (between x and array element) used. Let's assume we will adopt that as the unit time cost of the linear search function.

We now have an array of size n, with elements in range of [0,max], in ascending order and max >= n-1. Using your knowledge in probability, what is the estimated average time cost for using the linear search function above to search for x, where x is in range of [0,max]? Show your derivations and assumptions.

Please write your derivations and assumptions and final formula below:

Answer 1

More formal proof: Assume that the input has uniform probability and the the size of the array is n. Let X be a random variable denoting the number of comparisons. Then p(X= x) will denote the probability that we do x comparisons. Since the distribution is uniform, p(X = x) = 1/n. Once we formally defined our probability distribution now we can calculate the average number of comparisons in the linear search. What we do is compute the expected value

So average probability is (n+1)/2

Informally:

First assume input is uniformly distributed. More precisely it is (n+1)/2. When you search for a particular element x in an array of size n, that element may be located at the position either 1, or 2, …… or n. When we search we check each element in the array and compare it with x, and so when we reach kth element of the array we have already done k comparisons.

If it is at 1 then you find it in 1 comparison, if it is at 2, you find it in 2 comparisons, ……, if it is at n then you do n comparison in order to find it. In order to average it you sum the total number of comparisons 1+2+⋯+n = (n+1)n/2 and divide it by n (size of the array) resulting in (n+1)/2