Code kata 1 - CodeHub

Functional JS binary search.js

const INVALID = -1;

const binarySearch = (target,  arr) => {
  const start = 0;
  const finish = arr.length - 1;
  const middle = Math.floor((start + finish) / 2);
  
  console.log(arr);
  console.log('middle value: ',arr[middle]);
  
  if(arr[middle] === target){
    return middle;
  }
  
  if(start >= finish || finish == 0){
    return INVALID;
  }
  
  if(arr[middle] > target){
    let index = binarySearch(target, arr.slice(0, middle));
    console.log('index ',index);
    
    return (index !== INVALID)? index : 0 ;
  }else{
    let index = binarySearch(target, arr.slice(middle+1));
    console.log('index ',index);
    
    return(index !== INVALID)? index + middle+1 : index;
  }
}

const arr  = [1,3,4,5,6,7,9,11];
const targetValue =6;

console.log('RESULT: ',binarySearch(targetValue, arr, 0));

Iterative JS binary search.js

const binarySearch = (target, orderedArray) => {
  let start = 0;
  let finish = orderedArray.length - 1;
  let middle  = Math.floor((start + finish)/2);
  
  console.log('target value ', target);
  
  while(orderedArray[middle] !== target && start < finish){
    
    console.log('===');
    console.log('start index ',start);
    console.log('finish index',finish);
    console.log('middle index',middle);
    console.log('middle value ',orderedArray[middle]);
    
    if(orderedArray[middle] > target){
      // smaller
      finish = middle - 1;
    }else{
      // bigger
      start = middle + 1;
    }
    
    middle  = Math.floor((start + finish)/2);
  }
  
  return (orderedArray[middle] === target)? middle : -1;
}

const arr  = [1,3,4,5,6,7,9,11];
const targetValue = 11;

console.log(binarySearch(targetValue, arr));

Recursive JS binary search.js

const binarySearch = (target, start, finish, orderedArray) => {
  const middle = Math.floor((start + finish) / 2);
  
  if(orderedArray[middle] ===  target){
    return middle;
  }
  
  if(start >= finish){
    return -1;
  }
  
  if(orderedArray[middle] < target){
    return binarySearch(target, middle +1, finish, orderedArray);
  }else{
    return binarySearch(target, start, middle -1, orderedArray);
  }
}

const arr  = [1,3,4,5,6,7,9,11];
const targetValue = 3;

console.log(binarySearch(targetValue, 0, arr.length, arr));