利用递归去实现，要注意终止临界条件，否则会发生堆栈内存溢出的情况。
递归版本：
function binarySearch(arr, target, start, end) {
var idx = Math.floor((start + end) / 2);
if (idx == start && arr[idx] != target) {
return -1;
} else if (idx == start && arr[idx] == target) {
return idx;
}
if (target < arr[idx]) {
return binarySearch(arr, target, start, idx);
} else if (target > arr[idx]) {
return binarySearch(arr, target, idx, end);
} else {
return idx;
}
}
理论上任何递归可以解决的事情都可以通过迭代循环去解决，只是复杂度的问题。
非递归版本：
function binarySearch(arr, target, start, end) {
while(end-start >1){
var idx = Math.floor((start + end) / 2);
if (target < arr[idx]) {
end = idx;
} else if (target > arr[idx]) {
start = idx
} else {
return idx;
}
}
if(arr[end] == target) return end;
if(arr[start] == target) return start;
return -1;
}
