public boolean searchint A int target for int i 0 i

public boolean search(int[] A, int target){

for (int i = 0; i<A.length; i++){

if (target == A[i]) return true;

if (target < A[i] return false;

}

return false;

}

Derive an exact formula in n(not Big O) for the average number of target-to-element comparisons for successful searches on an array of size n.

how to derive  the formula of the average case of the sequential search on sorted array?

Solution

Just know how search works.
1) we simply traverse from element to another element from the first item in the list just by using FOR loop.
2) we just go from element to next element of array, and we are following the sequential ordering until our two condition will not be satisfied :
   a)we either find element what we are looking for.
   b)As this array is sorted , we already know that the item we were searching will never be less then current item we are currently on in current for loop interation.so we keep checking it.
           ex.) int [] arr = {10, 20, 30, 40,50};
               if value that needs to be find is 25. then we will never be after 30 and also we didnt found it yet.        As in sorted array all elements is pre sorted, then in this condition we simply return false.