A programmer writes a program to find an element in the array A[5] with the elements:8 30 40 45 70 the program is run to find a number X,that is found in the first iteration of binary search.what is the value of X?
Answers
The value of X is 40.
To understand this question, first we need to understand how binary search works.
Binary search usually employs the use of three variables, which can be named as ul (upper limit) , ll (lower limit), mid (middle element).
So, binary search slices the search domain into half with each pass.
And how it's done is by assigning ul the value of the last index of array, ll the value of first index of the array which is usually 0 and then assigning mid = (ul+ll)/2.
Now, with each iteration, first the element at mid is checked for equality with the search term.
If it's a match, the respective decisions are taken and the search is hence complete.
If not, then the search term is compared with the term at mid and search domain for next iteration is adjusted by shifting either ll or ul to mid.
Now coming back to the question, if the number is found in the first iteration of the given array, then it means that the element is at the mid(i.e.(0+4)/2).
So the number which was searched is A[2], which is 40.