Search a sorted 2D matrix [duplicate]

by

init: m[1..n(rows),1….m(columns)]

i=n,j=1

Start at (i,j):

STEP 1) if the value equals m(i,j) return (i,j)
STEP 2) if the value > m(i,j) go to step 1 with j+=1
STEP 3) else go to step 1 with i-=1

at each step if j or i is out of bound return no-solution.

The complexity of this solution is O(n+m) in case n=m the complexity is O(n)

I wonder if there is a log(n*m) solution like in binary search

EDIT another possible solution:

STEP 1)take the middle (n/2,m/2) of the matrix and compare it to the value
STEP 2) if the value equals m(i,j) return (i,j)
STEP 3) if the value is higher you can get rid from the first quarter  
STEP 4) if the value is lower you can get rid from the forth quarter
STEP 5) split the 3 other quarters to 2, a rectangle and a box, 
        send those both items to step 1 in a recursive manner

I am not sure about the efficiency of this solution:
if R = N*M then T(R) = T(R/2) + T(R/4) + O(1)

More Related Contents:

  1. How do you rotate a two dimensional array?
  2. Why is quicksort better than mergesort?
  3. Which sort algorithm works best on mostly sorted data? [closed]
  4. Data structures for loaded dice?
  5. Merge Sort a Linked List
  6. Quicksort: Choosing the pivot
  7. How to implement a queue using two stacks?
  8. Natural Sorting algorithm
  9. Compute the minimal number of swaps to order a sequence
  10. Computing set intersection in linear time?
  11. How to delete in a heap data structure?
  12. What is the difference between tree depth and height?
  13. Which parallel sorting algorithm has the best average case performance?
  14. How Do I Choose Between a Hash Table and a Trie (Prefix Tree)?
  15. Fast algorithm implementation to sort very small list
  16. Sorting in linear time? [closed]
  17. median of three values strategy
  18. Sorting an array with minimal number of comparisons
  19. O(klogk) time algorithm to find kth smallest element from a binary heap
  20. Write a program to find 100 largest numbers out of an array of 1 billion numbers
  21. Skip List vs. Binary Search Tree
  22. How can I return an array of struct in solidity?
  23. Why are hash table expansions usually done by doubling the size?
  24. Algorithm for merging two max heaps?
  25. Comparison-based ranking algorithm
  26. Why is bubble sort O(n^2)?
  27. Why is vector array doubled?
  28. Finding connected components of adjacency matrix graph
  29. Stable separation for two classes of elements in an array
  30. How to apply binary search O(log n) on a sorted linked list?

Leave a Comment