Как правильно построить логику для поиска по массивам?
Если отсортировать по идентификатору, то потом можно просто идти по двум спискам от начала к концу и сверять их по идентификаторам товаров.
Если в свежем списке есть идентификатор, а в старом нет, то продуктов добавился, если наоборот то удалился. За счёт того что массивы отсортированы сравнение можно выполнить за один проход.
var sorted_fruits_2016 = fruits_2016.sort(sortById);
var sorted_fruits_2017 = fruits_2017.sort(sortById);
var sorted_fruits_2018 = fruits_2018.sort(sortById);

var result_2016_2017 = compare(sorted_fruits_2016, sorted_fruits_2017);
var result_2017_2018 = compare(sorted_fruits_2017, sorted_fruits_2018);

function compare(oldArr, newArr) {
  var deleted = [], added = [], notChanged = [];
  var innerIndex = 0;

  if (!newArr.length) {
    return {
      added: added,
      deleted: oldArr,
      notChanged: notChanged
    };
  }

  for (var i = 0; i < newArr.length; i++) {
    if (innerIndex >= oldArr.length - 1) {
      added.push(newArr[i]);
      continue;
    }

    for (var j = innerIndex; j < oldArr.length; j++) {
      var newElId = newArr[i][0];
      var oldElId = oldArr[j][0];
      
      if (newElId > oldElId) {
        deleted.push(oldArr[j]);
      } else if (newElId < oldElId) {
        added.push(newArr[i]);
        innerIndex = j;
        break;
      } else {
        notChanged.push(newArr[i]);
        innerIndex = j + 1;
        break;
      }
    }
  }
  

  return {
    deleted: deleted,
    added: added,
    notChanged: notChanged
  };
}

function sortById(a, b) {
  return a[0] - b[0];
}Демо.
 Если сравнений надо делать не много, а например по требованию пользователя, то можно сделать функцию обертку для сортировки и сравнения:var result = compare(fruits_2016, fruits_2017);

console.log('result', result);

function compare(oldArr, newArr) {
  var sortedOldArr = oldArr.sort(sortById);
  var sortedNewArr = newArr.sort(sortById);
  
  return compareSorted(sortedOldArr, sortedNewArr);
}

function compareSorted(oldArr, newArr) {
  var deleted = [], added = [], notChanged = [];
  var innerIndex = 0;
  
  if (!newArr.length) {
    return {
      added: added,
      deleted: oldArr,
      notChanged: notChanged
    };
  }

  for (var i = 0; i < newArr.length; i++) {
    if (innerIndex >= oldArr.length - 1) {
      added.push(newArr[i]);
      continue;
    }

    for (var j = innerIndex; j < oldArr.length; j++) {
      var newElId = newArr[i][0];
      var oldElId = oldArr[j][0];
      
      if (newElId > oldElId) {
        deleted.push(oldArr[j]);
      } else if (newElId < oldElId) {
        added.push(newArr[i]);
        innerIndex = j;
        break;
      } else {
        notChanged.push(newArr[i]);
        innerIndex = j + 1;
        break;
      }
    }
  }
  

  return {
    deleted: deleted,
    added: added,
    notChanged: notChanged
  };
}

function sortById(a, b) {
  return a[0] - b[0];
}Демо.