History: if an array has 9 elements in it, then using binary search, which index would be the middle index in first iteration ?

An array index always starts from 0th index, given there are 9 elements, the last index will be 8th. To find middle (0+8)/2 = 4. So 4 is final answer