0
\$\begingroup\$

example

given a number and two dimensional array the method will check if the number is in the array the array is quadratic circular size n x n and each quarter of the array contains bigger numbers that the previous quarter(picture added)

the code i wrote:

 public static boolean search(int matrix[][], int key)
{
    
  int start = 0;
  int ROWS = matrix.length;
  int COLS = matrix[0].length;
  int mid, row, col, value;
  int end = ROWS * COLS - 1;
  while (start <= end)
  {
    mid = start + (end - start) / 2;
    row = mid / COLS;
    col = mid % COLS;
    value = matrix[row][col];
 
    if (value == key)
      return true;
    if (value > key)
      end = mid - 1;
    else
      start = mid + 1;
  }
  return false;
}

my goal is to make this code as efficient as possible in terms of time complexity,can you help me to improve it? and what time complexity is it right now? (o)log n^2?

New contributor
user252016 is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
\$\endgroup\$
9
  • 1
    \$\begingroup\$ Given that the 2d array is not sorted either vertically or horizontally, how can a binary search that treats the input as a single array work? \$\endgroup\$
    – Eric Stein
    yesterday
  • \$\begingroup\$ (@EricStein: looks trivial enough to successfully implement.) \$\endgroup\$
    – greybeard
    yesterday
  • 1
    \$\begingroup\$ Welcome to Code Review@SE. Please implement a minimum of tests - Is each of the values present found? What's the result for a value not in the array? Please state whether array sizes always are powers of 2. \$\endgroup\$
    – greybeard
    yesterday
  • \$\begingroup\$ ive said the array is quadratic circular size n x n ,you can close the question seems like im not getting any real help here \$\endgroup\$
    – user252016
    16 hours ago
  • \$\begingroup\$ @greybeard comment indicates we would like to see the code that calls this code. We need to know that the code is working as intended, there are other sites that can help you debug. If you add code that shows the testing this is a great question. \$\endgroup\$
    – pacmaninbw
    15 hours ago

Your Answer

user252016 is a new contributor. Be nice, and check out our Code of Conduct.

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.