利用遞歸去實現(xiàn)补疑，要注意終止臨界條件瘦馍，否則會發(fā)生堆棧內(nèi)存溢出的情況欣喧。
遞歸版本：
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;
}
}
理論上任何遞歸可以解決的事情都可以通過迭代循環(huán)去解決腌零，只是復雜度的問題。
非遞歸版本：
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;
}
