The average case occurs when the element to be found is somewhere in the list (not at the first or last position), and we must search through a few levels of the binary division.
In each step, the array is divided by 2:
• After 1st step → n/2 elements
• After 2nd step → n/4 elements
• ...
• After k steps → 1 element
Average Time Complexity = O(log n)