SOURCE

// BinarySearch   n / 2^k = 1;
function binarySearch(key, array) {
    let start = 0;
    let end = array.length - 1;
    let m = ~~((start + end) / 2);
    const flag = array[end] > array[start];

    while(start < end && key !== array[m]) {
        if (key > array[m]) {
            flag ? start = m + 1 : end = m - 1;
        } else {
            flag ? end = m - 1 : start = m + 1
        }

        m = ~~((start + end) / 2);
    }

    return array[m] === key ? m : -1;
}

 console.log(binarySearch(2, [0, 1, 1, 2, 2]));
 console.log(binarySearch(19, [4, 3, 2, 1, 0]));


function findMatrix(arr, target){
// 取左下角值
  let y = arr.length - 1;   // y坐标
  let x = 0;                // x坐标
  
  return findMatrixCore(arr, target, y, x)
}

function findMatrixCore(arr, target, y, x){
  // array[y]不为undefined，array[y][x]才可以调
  if(arr[y] === undefined || arr[y][x] === undefined){
    return false
  }
  
  let temp = arr[y][x]
  if(target < temp){   // target小于左下角，则y-1
    return findMatrixCore(arr, target, y-1, x)
  }else if(target > temp){  // target大于左下角，则x+1
    return findMatrixCore(arr, target, y, x+1)
  }else{
    console.log('x', y, x)
    return true
  }
  
}

var arr = [
  [1, 2, 3],
  [4, 5, 6],
  [7, 8, 9]
]

console.log(findMatrix(arr, 8))