What is the probability of an element being found? What would the math probability formula look like for an element being found? What is the probabilistic analysis of an element being found?
I have been researching a lot for getting the Average Case of Binary Search Element found but I am not able to understand the content well. Any help will be appreciated. Thanks in advance.
For the people requesting more detail, hope this much detail is enough.
I'm trying to get the time complexity of a pseudo-code of Binary Search, Worst and Average Case. I have to create a table which shows how many times on average it will take to find an element, where the element does exist in the list.
table:
Code Line | Time
-------------------------------------
Let s = 1 | 1
Let e = A.length | 1
while s ≤ e do | X
m = ⌊(s+e)/2⌋ | X
if A[m] == v then | X
Return m | 1
else if A[m] < v then | Y
Let s = m + 1 | Y
else | Z
Let e = m – 1 | Z
Return unsuccessful. | 0
Where X is what I'm trying to find. I'm not sure how many time the Binary Search loop has to iterate to find the element on an average case.