First of all note that your recopying array slices makes this algorithm take as much or more work than just walking the whole array (which doesn't need to assume sorted first). If you want a binary search to be efficient, it is much better to pass an array reference and 2 indexes.

Secondly any time you hear the word "search", you should think to yourself, "hash lookup". Building a hash takes the same amount of work as scanning the array a fairly small number of times, and is a simple one-liner to code. Even when it isn't the most efficient approach, it is generally only off by a constant factor from the best, and doing better takes a lot of work. Become friends with the hash. Using it takes less work, is more efficient, and is more reliable.