JSFiddle - React, Tailwind, and code Playground

by stchangg

JavaScript

// binary sort

var array = [1,3,5,20,21];
var lower = 0;
var upper = array.length - 1;
var target = 21;

document.write(upper+"<br/>");

function binarySearch( array, lower, upper, target ) {
  document.write(lower + " " + upper + "<br/>");
  
  var range = upper - lower;
  // ensure upper > lower
  if ( range < 0 ) {
    return "limits reversed";
  }
  
    // confirm that array is sorted
  if ( array[upper] < array[lower] ) {
    return "not sorted";
  }
  
  // if the target is not in the array (upper == lower) && target != lower
  if ( range === 0 && target !== array[lower] ) {
    return "target not in array";
  }
  
  if ( range === 1 ) {
    if ( target === array[lower] ) {
      return lower;
    } else if ( target === array[upper] ) {
      return upper;
    } else {
      return "not in array";
    }
  }
  
  // find the center index (assumes we have a odd-sized array)
  var center = Math.floor((range)/2) + lower; 
  document.write(center + "<br/>");
  
  // if the target value is equal to the center value, we have found it!
  if ( target === array[center] ) {
    return center;
    
  // otherwise, if it's less than the center value, search [lower, center]
  } else if ( target < array[center] ) {
    return binarySearch( array, lower, center-1, target ); 
    
  // if it's greater, search [center, upper]
  } else {
    return binarySearch( array, center+1, upper, target );
  }

}

var ans = binarySearch( array, lower, upper, target );

document.write(ans);