Advertisement
Ritam_C

Young's Tableau

Mar 21st, 2021
133
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.24 KB | None | 0 0
  1. def bin_search(s, e, l, x):
  2.     if e >= s:
  3.         mid = s+(e-s)//2
  4.         if l[mid] == x:
  5.             return mid
  6.         elif l[mid] > x:
  7.             return bin_search(s, mid-1, l, x)
  8.         elif l[mid] < x:
  9.             return bin_search(mid+1, e, l, x)
  10.     else:
  11.         return -1            
  12.  
  13. def bin_s(s, e, l, x):
  14.     if e >= s:
  15.         mid = s+(e-s)//2
  16.         if l[mid][0] <= x and l[mid][m-1] >= x:
  17.             return mid
  18.         elif l[mid][0] > x:
  19.             return bin_s(s, mid-1, l, x)
  20.         elif l[mid][m-1] < x:
  21.             return bin_s(mid+1, e, l, x)
  22.     else:
  23.         return -1
  24.  
  25. def find(n, m, t, x):
  26.     px, py = -1, -1
  27.     if t[0][0] > x or t[n-1][m-1] < x:
  28.         return -1, -1
  29.     else:
  30.         px = bin_s(0, n-1, t, x)
  31.         if px != -1:
  32.             py = bin_search(0, m-1, t[px], x)
  33.        
  34.         return px, py
  35.  
  36. if __name__ == "__main__":
  37.     n = int(input())
  38.     m = int(input())
  39.     t = []
  40.     for i in range(n):
  41.         p = []
  42.         for j in range(m):
  43.             x = int(input())
  44.             p.append(x)
  45.         t.append(p)
  46.     x = int(input())
  47.     a, b = find(n, m, t, x)
  48.     if a == -1 or b == -1:
  49.         print("Not found")
  50.     else:
  51.         print("["+str(a)+", "+str(b)+"]")
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement