Variant of Binary Search

We can convert this problem to binary search by convert the 2D index to 1D index.

2D to 1D

a m * n matrix has m * n values. so, it is a 0 .. (m * n - 1) array.

a 10 * 8 matrix

(y)
 0   1   2   3   4   5   6   7   8   9
000 001 002 003 004 005 006 007 008 009  0 (x)
010 011 012 013 014 015 016 017 018 019  1
020 021 022 023 024 025 026 027 028 029  2
030 031 032 033 034 035 036 037 038 039  3
040 041 042 043 044 045 046 047 048 049  4
050 051 052 053 054 055 056 057 058 059  5
060 061 062 063 064 065 066 067 068 069  6
070 071 072 073 074 075 076 077 078 079  7

Note:

  • x here is from top to bottom, y is from left to right
  • this is for making code to be matrix[x][y]

056 is at matrix[5][6]

  • 5 (x) = 56 / 10 (width)
  • 6 (y) = 56 % 10 (width)

so convert index i to x, y:

  • x = i / width
  • y = i % width