Binary search on string in alphabetical order

Question

The code for a binary search on an ordered string by alphabetical orders seems to work. I am wondering if there is a better way to write this.

function binary_search(arr, letter){
 var first = 0;
 var middle = Math.floor(arr.length/2);
 var last = arr.length -1;
 while(true){
 var test = arr[last];
 if(arr[middle] === letter){
 return true
 }else if(arr[first] >= letter && letter < arr[middle]){
 last = middle -1;
 middle = Math.floor((first + last)/2);
 }else if (arr[middle] < letter && letter <= arr[last]){
 first = middle +1;
 middle = Math.floor((first + last)/2);
 }else {
 return false;
 }
 }
}
var str ="abcdefg"
console.log(binary_search(str, "g"));
console.log(binary_search(str, "a"));
console.log(binary_search(str, "e"));
console.log(binary_search(str, "z"));

• woxxom: It doesn't find M in a 26MB string built with new Array(26).fill(0).map((e,i)=>new Array(1e6).fill(String.fromCharCode(65 + i)).join('')).join('')

Answer 1

Binary search is usually simpler:

function binarySearch(haystack, needle) {
 var a = 0;
 var b = haystack.length - 1;
 if (needle < haystack[0] || needle > haystack[b]) {
 return false;
 }
 while (a < b - 1) {
 var c = (a + b) / 2 |0;
 if (needle < haystack[c]) {
 b = c;
 } else {
 a = c;
 }
 }
 return haystack[a] === needle || haystack[a+1] === needle;
}