Question
Consider the following pseudo code algorithm for searching an arrayA
input: an array A and a search item M
Output: True if M is in A and False if M is not in A
1. i is assigned the value 0;
2. While (i<Length(A))
2.1 Assign i the value i+1;
2.2 If(A(i) equals M) then Print True; Halt.
3. EndWhile;
4. Print False;
5 Halt.
Suppose that A contains the entries 4,3,0,9,3 in this order and Mis equal to 3. How many times will the test in line 2.2 be carriedout?
Explain how binary search is the basis of a faster algorithm forseraching a large array, under the assumption that the array issorted such that the entries of the array are in increasingorder
Give explanation please, in the simplest way
thanks
Explanation / Answer
Suppose that A contains the entries 4,3,0,9,3 in this orderand M is equal to 3. How many times will the test in line 2.2 becarried out? The test in line 2.2 is carried out only once. In line 2.1...the value of i is increased to 0+1 i.e 1 now A[1] equals 3..therefore after this the program halts therefore it is compared only once. Explain how binary search is the basis of a fasteralgorithm for searching a large array, under the assumption thatthe array is sorted such that the entries of the array are inincreasing order?? In binary search, we will compare the given number with the middleelement or median. if the number equals the middle element we will return TRUE if the number is smaller than median, next time we will onlytake the list of elements from 0 to median if the number is greater than median, next time we will only takeelements from median to end of list Eg: if the list is < 1, 2, 3, 4, 5> , wewant to search for 5 1) we compare 5 with middle element 3 as 3