import java.math.BigInteger;
import static java.math.BigInteger.ZERO;
import static java.nio.charset.StandardCharsets.US_ASCII;
import static java.util.Arrays.copyOf;
import static java.lang.Math.max;

// https://stackoverflow.com/a/47048431
static int interpolate(String ys, String xs, String iOfTs, int id) {
  int maxLen = max(max(xs.length(), ys.length()), iOfTs.length());
  BigInteger x = new BigInteger(1, copyOf(xs.getBytes(US_ASCII), maxLen));
  BigInteger y = new BigInteger(1, copyOf(ys.getBytes(US_ASCII), maxLen));
  BigInteger iOfT = new BigInteger(1, copyOf(iOfTs.getBytes(US_ASCII), maxLen));
  BigInteger d = BigInteger.valueOf(id);
  BigInteger den = x.subtract(y);
  return ZERO.equals(den) ? 0 : (int) d.multiply(iOfT.subtract(y)).divide(den).longValue();
}

public String stringAtLine(lineNumber) {
  return swhToNodeMap.readLine(lineNumber).split(" ");
}

public long getNode(SwhId swhId) {
  long start = 0;
  long end = nbIds;
  String target = swhId.toString();

  while (start <= end) {
    String[] start_string = stringAtLine(start)[0];
    String[] end_string = stringAtLine(end)[0];
    long lineNumber = start + interpolate(start_string, end_string, target, start - end);

    String[] parts = stringAtLine(lineNumber);
    String currentSwhId = parts[0];
    long currentNodeId = Long.parseLong(parts[1]);

    int cmp = currentSwhId.compareTo(target);
    if (cmp == 0) {
      return currentNodeId;
    } else if (cmp < 0) {
      start = lineNumber + 1;
    } else {
      end = lineNumber - 1;
    }
  }

  return -1;
}