A good number of interview questions require you to constantly split an array/string in half.
This is relatively easy to achieve when the array count is odd.
However when the count is even, it’s not as easy.
let a = [1,3,8,10,22] // middle index is 2
let b = [1,3,8,10] // middle index is 1.5 which is non-existent. So what now?
Most important thing to note is: There’s no such thing as “middle index” when the count is even, I mean there’s two middles in that case. I guess the “middle” are those two indices. But then you have to pick one. For this reason it’s often better to think of it as a pivot because it’s really the 2nd index. The 2nd index isn’t the middle index of a 4 element array.
Moving away from ‘find the middle index’ to a ‘find the pivot index which we’ll use as a middle index’ helped me understand the concept better.
After that, you typically just need logic that handles all three cases of before, after and the index itself or similarly lower, greater, equal to the index itself.
Example - Flip an array
[0,0,2,2] -> [2,2,0,0]
The general way to calculate the pivot index is:
let pivotIndex = (lower + upper) / 2
let pivotIndex = lower + (upper - lower) / 2 // This approach helps avoid integer overflow. In swift we get the rounded number automatically.
[0,0,2,2]
pivot index = (0 + 3) / 2 = 1
[0,0,2,2]
|
pivot
- indexes before pivot: swap
- indexes equal to pivot: swap
- indexes after pivot: ignore, as they’re already swapped
Example - Binary Search
Ask
[2, 7, 20, 24, 40, 99]
find 99
1st Iteration
pivot index = (0 + 5) / 2 = 2
[2, 7, 20, 24, 40, 99]
| | |
left pivot right
2nd Iteration
pivot is now index: 4
. It’s now actually the middle of its range.
[2, 7, 20, 24, 40, 99]
| | |
left pivot right
3rd Iteration
pivot is now index: 5
. left and right index are also index: 5
[2, 7, 20, 24, 40, 99]
|
left
pivot
right
Different way of seeings things
We’re not always cutting the array/section in half.
- For odd ranges: you calculate the middle index correctly. Yet you’re not precisely cutting the section in half. Example:
[2, 7, 20, 24, 40]
pivot point is index: 2
.
-
You will drop three items:
(20, 24,40)
if you’re looking for2
or7
. -
You will drop three items:
(2, 7, 20)
if you’re looking for24
or40
. -
You will drop four items:
(2, 7, 24, 40)
if you’re looking for20
. -
For even ranges: You’re not really calculating a middle. You may or may not end up precisely cutting the section in half. Example:
[2, 7, 20, 24, 40, 99]
pivot point is index: 2
.
- You will drop four items:
(20, 24, 40, 99)
if you’re looking for2
,7
. - You will drop three items:
(2, 7, 20)
if you’re looking for24
,40
,99
. - You will drop five items:
(2, 7, 24, 40, 99)
if you’re looking for20
.
👆 isn’t to tell you think how many you’re dropping. It’s just once you realize you’re not always cutting in half, things actually start to make more sense. Personally it helped me visualize what’s happening easier…
Conclusion
Don’t think of middle index as the absolute middle index. Think of it more as a pivot point. Things just work as long as you have correct logic to handle all varying cases (less than, equal to, greater than)
Acknowledgments
Special thanks to Mira, Suyash and Arthur for answering my questions so I can put this post together.