// Example Input 1:
let phoneBook = [{name: 'Ann', number: "123-456-7890"},  {name: 'John', number: "234-567-8901"}, {name: 'John', number: "345-678-9012"} ];
// Phone book is alphabetized

// ON Soln
// container for match {}
// loop through the array
  // find match, save match to container
// return match.number

function searchPhoneBookON(book, name) {
  if (!book || !name) {
    return 'no match found';
  }

  let lastMatch = {};

  book.forEach(listing => {
    if ((listing.name).toLowerCase() === name.toLowerCase()) {
      lastMatch = listing;
    }
  })

  return lastMatch.number;
}

// ON Version Test
console.log('O(N)', 'John', searchPhoneBookON(phoneBook, 'John'));

// More optimized solution
// main function
  // holder for last match
  // run helper function on book
  // return info from holder

// helper
// find the middle
// check if it matches or if it's higher
  // if it matches, save match
  // check the right until
// if it's lower
  // check the left.


function sPhoneB(book, name) {
  if (!book || !name) {
    return 'match not found';
  }
  let lastMatch = {};
  _sPhoneB(book, name);
  return lastMatch.number;


  function _sPhoneB(book, name) {
  if (book.length === 0 ) {
    return;
  } else if (book.length === 1) {
    let listing = book[0].name;
    if (listing.localeCompare(name) === 0) {
      lastMatch = book[0];
    }
  } else {
    let middle = Math.floor(book.length/2)

    let middleName = book[middle].name;

    if (name.localeCompare(middleName) >= 0) {
      if (middleName.localeCompare(name) === 0) {
        lastMatch = book[middle];
      }
      let right = book.slice(middle);
      _sPhoneB(right, name);
    } else if (name.localeCompare(middleName) < 0) {
      let left = book.slice(0, middle);
      _sPhoneB(left, name);
    }
  }
}
}

// Log N Test
console.log('log N', 'Ann', sPhoneB(phoneBook, 'Ann'));