#include <iostream>
using namespace std;
 
 
const int SIZE = 4;
const int NOT_FOUND = -1;
int  binarySearch(int mat[][SIZE], int &line , int num);
int main()
{
    int num, index,  mat[SIZE][SIZE] = { 0,1,5,2,
                                         8,6,7,7,
                                         11,7,7,10,
                                         11,12,9,11 };
    int line = sizeof(mat) / sizeof(mat[0][0]);
    cout << "please type a number to search: " << endl;
    cin >> num;
    index = binarySearch(mat, line, num);
    if (index == NOT_FOUND)
        cout << "The value: " << num << "doesn't exist in the array\n";
    else
        cout << "The value: " << num << " exists in line " << line+1 <<" and column: " << index+1 << endl;
	return 0;
}
 
 
int binarySearch(int mat[][SIZE], int &line, int num)
{
    int j;
    for (j = 0; j < SIZE; j++)
    {
        int low = 0, high = SIZE - 1, middle;
        while (low <= high)
        {
            middle = (low + high) / 2;
                if (num == mat[middle][j])
                {
                    line = middle;
                    return j;
                }
                else if (num < mat[middle][j])
                    high = middle - 1;
                else
                    low = middle + 1;
        }
    }
    return NOT_FOUND;
}

I2luY2x1ZGUgPGlvc3RyZWFtPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKCmNvbnN0IGludCBTSVpFID0gNDsKY29uc3QgaW50IE5PVF9GT1VORCA9IC0xOwppbnQgIGJpbmFyeVNlYXJjaChpbnQgbWF0W11bU0laRV0sIGludCAmbGluZSAsIGludCBudW0pOwppbnQgbWFpbigpCnsKICAgIGludCBudW0sIGluZGV4LCAgbWF0W1NJWkVdW1NJWkVdID0geyAwLDEsNSwyLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIDgsNiw3LDcsCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgMTEsNyw3LDEwLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIDExLDEyLDksMTEgfTsKICAgIGludCBsaW5lID0gc2l6ZW9mKG1hdCkgLyBzaXplb2YobWF0WzBdWzBdKTsKICAgIGNvdXQgPDwgInBsZWFzZSB0eXBlIGEgbnVtYmVyIHRvIHNlYXJjaDogIiA8PCBlbmRsOwogICAgY2luID4+IG51bTsKICAgIGluZGV4ID0gYmluYXJ5U2VhcmNoKG1hdCwgbGluZSwgbnVtKTsKICAgIGlmIChpbmRleCA9PSBOT1RfRk9VTkQpCiAgICAgICAgY291dCA8PCAiVGhlIHZhbHVlOiAiIDw8IG51bSA8PCAiZG9lc24ndCBleGlzdCBpbiB0aGUgYXJyYXlcbiI7CiAgICBlbHNlCiAgICAgICAgY291dCA8PCAiVGhlIHZhbHVlOiAiIDw8IG51bSA8PCAiIGV4aXN0cyBpbiBsaW5lICIgPDwgbGluZSsxIDw8IiBhbmQgY29sdW1uOiAiIDw8IGluZGV4KzEgPDwgZW5kbDsKCXJldHVybiAwOwp9CgoKaW50IGJpbmFyeVNlYXJjaChpbnQgbWF0W11bU0laRV0sIGludCAmbGluZSwgaW50IG51bSkKewogICAgaW50IGo7CiAgICBmb3IgKGogPSAwOyBqIDwgU0laRTsgaisrKQogICAgewogICAgICAgIGludCBsb3cgPSAwLCBoaWdoID0gU0laRSAtIDEsIG1pZGRsZTsKICAgICAgICB3aGlsZSAobG93IDw9IGhpZ2gpCiAgICAgICAgewogICAgICAgICAgICBtaWRkbGUgPSAobG93ICsgaGlnaCkgLyAyOwogICAgICAgICAgICAgICAgaWYgKG51bSA9PSBtYXRbbWlkZGxlXVtqXSkKICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICBsaW5lID0gbWlkZGxlOwogICAgICAgICAgICAgICAgICAgIHJldHVybiBqOwogICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgZWxzZSBpZiAobnVtIDwgbWF0W21pZGRsZV1bal0pCiAgICAgICAgICAgICAgICAgICAgaGlnaCA9IG1pZGRsZSAtIDE7CiAgICAgICAgICAgICAgICBlbHNlCiAgICAgICAgICAgICAgICAgICAgbG93ID0gbWlkZGxlICsgMTsKICAgICAgICB9CiAgICB9CiAgICByZXR1cm4gTk9UX0ZPVU5EOwp9

MTA=

10