tl;dr: 1. Avoid branching by always reducing the search range from n to n-n/2 (never n/2). 2. Preprocess the input (a sorted array) to Eytzinger order: Middle

tl;dr: 1. Avoid branching by always reducing the search range from n to n-n/2 (never n/2). 2. Preprocess the input (a sorted array) to Eytzinger order: Middle element, then first and third quartile elements etc. Now, if your search checks an element at position k, it will next want to look at either position 2k or 2k+1. 3. Some minor tweaks like aligned storage and rounding up size to a power of 2.