const NOT_FOUND = "not found"

// Plain binary search implementation
//    BTW: this one contains a bug, try finding it =)
function binarySearch(ar, el) {
  let m = 0, n = ar.length - 1
  while (m <= n) {
    const k = (n + m) >> 1
    if (el > ar[k])
      m = k + 1
    else if(el < ar[k])
      n = k - 1
    else
      return k
  }
  return -m - 1
}

// Matrix view class, allows working with rectangular matrix subsets
class MatrixView {
  constructor(source, left = 0, top = 0, right = undefined, bottom = undefined) {
    this.source = source
    this.left = left
    this.top = top
    this.bottom = bottom || source.length
    this.right = right || (source.length > 0 ? source[0].length : 0)
  }

  // Extracts diagonal from current subset
  * extractDiagonal() {
    for (let [i, j] = [this.top, this.left]; i < this.bottom && j < this.right; i++, j++)
      yield this.source[i][j]
  }

  // Extracts row at given index and inner start
  * extractRow(rowIndex = 0, startIndex = 0) {
    for (let i = this.left + startIndex; i < this.right; i++)
      yield this.source[this.top + rowIndex][i]
  }

  // Extracts column at given index and inner start
  * extractColumn(columnIndex = 0, startIndex = 0) {
    for (let i = this.top + startIndex; i < this.bottom; i++)
      yield this.source[i][this.left + columnIndex]
  }

  // Converts local coordinates to global
  toSourceCoordinates([x, y]) {
    return [this.top + x, this.left + y];
  }

  // Performs matrix binary search
  binarySearchMatrix(el) {

    // Our view is empty => not found
    if (this.top >= this.bottom || this.left >= this.right)
      return NOT_FOUND;

    // Our view is a row => do a binary search
    if (this.top + 1 === this.bottom) {
      const rowIndex = binarySearch([...this.extractRow()], el)
      return rowIndex >= 0 ? this.toSourceCoordinates([0, rowIndex]) : NOT_FOUND
    }

    // Our view is a column => do a binary search
    if (this.left + 1 === this.right) {
      const columnIndex = binarySearch([...this.extractColumn()], el)
      return columnIndex >= 0 ? this.toSourceCoordinates([columnIndex, 0]) : NOT_FOUND
    }

    // Search for the elment on a diagonal
    let diagonalIndex = binarySearch([...this.extractDiagonal()], el)

    // Return if it's found
    if (diagonalIndex >= 0)
      return this.toSourceCoordinates([diagonalIndex, diagonalIndex])

    // Pick on a diagonal, after which our element should be
    diagonalIndex = -diagonalIndex - 2

    // If element could be outside diagonal => it's outside matrix => not found
    if (diagonalIndex === -1 || diagonalIndex === this.right || diagonalIndex == this.bottom)
      return NOT_FOUND

    const diagonalCoords = this.toSourceCoordinates([diagonalIndex, diagonalIndex])

    // Search for element in upper-right matrix subset
    let t = new MatrixView(this.source, diagonalCoords[1] + 1, this.top, this.right, diagonalCoords[0] + 1)
    let result = t.binarySearchMatrix(el);
    if (result !== NOT_FOUND) return result;

    // Search for element in bottom-left matrix subset
    t = new MatrixView(this.source, this.left, diagonalCoords[0] + 1, diagonalCoords[1] + 1, this.bottom)
    result = t.binarySearchMatrix(el);
    if (result !== NOT_FOUND) return result;

    // Otherwise
    return NOT_FOUND;
  }
}

function binarySearchMatrix(ar, el) {
  return new MatrixView(ar).binarySearchMatrix(el)
}

const sortedMatrix = [
  [  0,  1,  2,  3,  4,  5],
  [ 10, 10, 20, 21, 22, 23],
  [ 20, 21, 30, 31, 32, 33],
  [ 30, 31, 40, 41, 42, 43],
  [ 40, 41, 50, 51, 52, 55],
  [ 50, 51, 60, 61, 62, 63],
]

const n = sortedMatrix.length

// Search for all elements in matrix
for (let i = 0; i < n; i++)
  for (let j = 0; j < n; j++) {
    let result = binarySearchMatrix(sortedMatrix, sortedMatrix[i][j])
    if (sortedMatrix[i][j] !== sortedMatrix[result[0]][result[1]])
      console.log(`ERROR searchin for ${sortedMatrix[i][j]}, returned ${result}`)
  }

// Search for elements outside matrix
for (let i = -10; i <= 70; i++) {
  let result = binarySearchMatrix(sortedMatrix, i)
  console.log(`Searched for ${i} returns ${result}`)
}