3 ms·
int middle = (min + max) >> 1; This will work for n < MAX_INT/2. For larger n, middle must be calculated as min + ((max - min) >> 1), which is one subtraction
by desdiv 12y ago
int middle = (min + max) >> 1;
This will work for n < MAX_INT/2. For larger n, middle must be calculated as min + ((max - min) >> 1), which is one subtraction per iteration more.
Making middle an unsigned int should make (min + max) >> 1 work for all int values.
- tromp 12y agoThat's not guaranteed to work. If min+max is a negative signed int, then the result of right shifting is implementation dependent. Instead, you could do int middle = (unsigned)(min + max) >> 1; Still, this relies on the original indices falling in the non-negative range of signed ints.