find an element in a sorted matrix [duplicate]

by

Start in the bottom-left corner of your matrix. Then go to the right until you find the exact number (done), or until you find a number that is bigger.

Then you go upwards in the matrix until you find the exact number (done), or until you find a number that is too small.

Then again you move to the right, … and so on until you found the number or until you reach the right-side or top of your matrix.

The following images contain some examples, using an Excel table showing the target number in green, and the path that is followed in yellow.

enter image description here

enter image description here

In the last example we look for 207, which isn’t in the matrix:

enter image description here

This is just the algorithm. The coding is left for you as an exercise 🙂

EDIT: When starting on the bottom row, a binary search might give a better starting point. For the rest of the algorithm it probably doesn’t matter.

More Related Contents:

  1. How to remove repetition in output results in this code
  2. Write a program that takes an array/arraylist of integer and finds longest sub array/arraylist whose entries are equal [closed]
  3. Finding the max/min value in an array of primitives using Java
  4. Connect 4 check for a win algorithm
  5. Quickest way to find missing number in an array of numbers
  6. Finding the second highest number in array
  7. Java, find intersection of two arrays
  8. Java, Shifting Elements in an Array
  9. Find duplicate element in array in time O(n)
  10. All possible combinations of an array
  11. Flatten nested arrays in java
  12. How to find the only number in an array that doesn’t occur twice [duplicate]
  13. Generate Random Numbers in Array [duplicate]
  14. Interview question – Search in sorted array X for index i such that X[i] = i
  15. Generating all permutations of a given string
  16. Which Java Collection should I use?
  17. Cannot create an array of LinkedLists in Java…?
  18. How to convert an int array to String with toString method in Java [duplicate]
  19. How to calculate elapsed time from now with Joda-Time?
  20. How to get unique values from array
  21. Fast algorithm for searching for substrings in a string
  22. How does the Java array argument declaration syntax “…” work?
  23. Converting string arrays into Map
  24. In Java, how do I efficiently and elegantly stream a tree node’s descendants?
  25. get closest value to a number in array
  26. Wav file convert to byte array in java
  27. How to determine if binary tree is balanced?
  28. Can SHA-1 algorithm be computed on a stream? With low memory footprint?
  29. Java Smooth Color Transition
  30. Compare two arrays of primitives in Java?

Leave a Comment