0

image

Matrix is in the form of 

10 | 13 | 43 | 61 | 67 | 83      
14 | 24 | 47 | 71 | 3  | 94  
22 | 33 | 51 |82  | 88 | 96  
27 | 41 | 52 | 84 | 92 | 99  
38 | 45 | 52 | 90 | 95 | 101  
105|111 |121 |133 |144 |149

Find 43,60,144

Given a 2D array with numeric values that are sorted row wise 4 column wise.Find if a value exists in the array using binary search.

I have traced it by binary search in image. 1st try: I have traced it by first finding the midpoint(51).After finding the first midpoint,I have divided the matrix in two parts. 1st part is the upper half (10-51 diagonally) and 2nd is the remaining part.Can I divide the matrix in such way(1st try)?

2nd try:I have again taken a midpoint(51) and divided into lower and upper half.Upper half and lower half taken by diagonal numbers.

I am not able to find th values that are given. Is there anyother condition through which I can find numbers:43,60,144 ?

2D array:

 int no[6][6]={{10,13,43,61,67,83},
  {14,24,47,71,73,94},  
  {22,33,51,82,88,96}, 
  {27,41,52,84,92,99},
  {38,45,60,90,95,101},
  {105,111,121,133,144,149}
  };
Ked
  • 11
  • 7
  • I am not able to see any 2D array. Can you post your actual array.if it's in array format it's really easy to do what you want. – Alive to die - Anant Oct 09 '17 at 04:53
  • Yes.I will post 2D array in few minutes. – Ked Oct 09 '17 at 04:56
  • @ked do you want to know "43,60,144" all of them exist or any of them exist – shashi Oct 09 '17 at 05:02
  • If any of them exists.Since all are present in matrix.,it should show all of them. – Ked Oct 09 '17 at 05:05
  • Possible duplicate of [Given a 2d array sorted in increasing order from left to right and top to bottom, what is the best way to search for a target number?](https://stackoverflow.com/questions/2457792/given-a-2d-array-sorted-in-increasing-order-from-left-to-right-and-top-to-bottom) – DAle Oct 09 '17 at 08:08
  • Yes,its the same,but I have tried it diagonally once.Can you trace the algorithm for me for finding 43 in matrix.It will be very helpful for me. – Ked Oct 09 '17 at 08:22

1 Answers1

0

I would recommend looking at the linear algorithm first. It is simple and has O(n+m) complexity. Let's simulate it step by step. We start from the left bottom corner. Then if the query number is less than the number in the current position we move up, else if it is bigger we move right.

10  13  43  61  67  83
14  24  47  71  73  94  
22  33  51  82  88  96 
27  41  52  84  92  99
38  45  60  90  95  101
105 111 121 133 144 149

We start from the left bottom corner.
43 < 105, so all numbers in this row will be bigger than 43. Move up. 

10  13  43  61  67  83
14  24  47  71  73  94  
22  33  51  82  88  96 
27  41  52  84  92  99
38  45  60  90  95  101

43 > 38, so all numbers in this column will be less than 43. Move right. 

13  43  61  67  83
24  47  71  73  94  
33  51  82  88  96 
41  52  84  92  99
45  60  90  95  101

43 < 45. Move up.

13  43  61  67  83
24  47  71  73  94  
33  51  82  88  96 
41  52  84  92  99

43 > 41. Move right.

43  61  67  83
47  71  73  94  
51  82  88  96 
52  84  92  99

43 < 52. Move up.

43  61  67  83
47  71  73  94  
51  82  88  96

43 < 51. Move up.

43  61  67  83
47  71  73  94

43 < 47. Move up.

43  61  67  83

43 = 43. Bingo!

DAle
  • 8,990
  • 2
  • 26
  • 45