Elite Day-8 Program-1.txt

There is a board with M*N size. 
The board contains M*N blocks of 1*1 size.
Each block is printed a number on it.

You will be given a number, your task is to find whether the number is printed on 
any of the blocks or not. If found print true, otherwise print false.

NOTE: 
- The numbers printed on the board in each row are in increasing order. 
- Next row starting number is greater than the last number of the previous row.

Constarint:
-----------
Can you solve it in log(M)+ log(N) time. 


Input Format:
-------------
Line-1 -> Two integers M and N, board size.
Next M lines -> N space separated integers.
Last Line -> An integer T, number to search.

Output Format:
--------------
Print a boolean value, 'true' if number found.
otherwise, 'false'.


Sample Input-1:
---------------
4 4
1 3 6 10
12 15 19 23
24 28 32 36
37 41 44 47
15

Sample Output-1:
----------------
true


Sample Input-2:
---------------
4 4
1 3 6 10
12 15 19 23
24 28 32 36
37 41 44 47
26

Sample Output-2:
----------------
false


using log(M)+log(N) complexity!

50/100:
def bin_search(l,n):
    low,mid=0,0
    high=len(l)-1
    while(high>=low):
        mid=(high+low)//2
        if(l[mid]<n):
            low=mid+1
        elif(l[mid]>n):
            high=mid-1
        else:
            return mid
    return -1
    
r,c=map(int,input().split())
l=[]
for i in range(r):
    l.append(list(map(int,input().split()))[:c])
n=int(input())

for i in range(len(l)):
    if(bin_search(l[i],n)!=-1):
        index=bin_search(l[i],n)
        break
        
l1=[]
for i in range(len(l)):
    l1.append(l[i][index])
# print(l1)

# print(bin_search(l1,n))

if(bin_search(l1,n)!=-1):
    print(True)
else:
    print(False)




100/100:
m,n=list(map(int,input().split()))
l=[]
for i in range(m):
    l.append(list(map(int,input().split())))
t=int(input())
s,e,f=0,m*n-1,1
while s<=e:
    mid=(s+e)//2
    if l[mid//n][mid%n]==t:
        print("true")
        f=0
        break
    if l[mid//n][mid%n]<t:
        s=mid+1
    else:
        e=mid-1
if f==1:
    print("false")