Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.*;
- public class Main {
- public static void main(String[] args) {
- // Example usage
- int[][] X = {
- {1, 2, 3},
- {4, 5, 6},
- {7, 8, 9}
- };
- int k = 5;
- int top_left_i = 0;
- int top_left_j = 0;
- int bottom_right_i = X.length - 1;
- int bottom_right_j = X[0].length - 1;
- Pair<Integer, Integer> result = find(X, k, top_left_i, top_left_j, bottom_right_i, bottom_right_j);
- if (result.getKey() == -1 && result.getValue() == -1) {
- System.out.println("Element not found.");
- } else {
- System.out.println("Element found at position (" + result.getKey() + ", " + result.getValue() + ").");
- }
- }
- public static Pair<Integer, Integer> find(int[][] X, int k, int top_left_i, int top_left_j, int bottom_right_i, int bottom_right_j) {
- int m_i = (top_left_i + bottom_right_i) / 2;
- int m_j = (top_left_j + bottom_right_j) / 2;
- if (X[m_i][m_j] == k) {
- return new Pair<>(m_i, m_j);
- }
- if (top_left_i == bottom_right_i && top_left_j == bottom_right_j) {
- return new Pair<>(-1, -1); // not found
- }
- if (top_left_i > bottom_right_i || top_left_j > bottom_right_j) {
- return new Pair<>(-1, -1); // not found
- }
- if (X[m_i][m_j] > k) {
- Pair<Integer, Integer> pos = find(X, k, top_left_i, top_left_j, m_i - 1, m_j - 1);
- if (!pos.equals(new Pair<>(-1, -1))) {
- return pos;
- }
- pos = find(X, k, m_i, top_left_j, bottom_right_i, m_j - 1);
- if (!pos.equals(new Pair<>(-1, -1))) {
- return pos;
- }
- pos = find(X, k, top_left_i, m_j, m_i - 1, bottom_right_j);
- if (!pos.equals(new Pair<>(-1, -1))) {
- return pos;
- }
- } else {
- Pair<Integer, Integer> pos = find(X, k, m_i + 1, m_j + 1, bottom_right_i, bottom_right_j);
- if (!pos.equals(new Pair<>(-1, -1))) {
- return pos;
- }
- pos = find(X, k, m_i + 1, top_left_j, bottom_right_i, m_j);
- if (!pos.equals(new Pair<>(-1, -1))) {
- return pos;
- }
- pos = find(X, k, top_left_i, m_j + 1, m_i, bottom_right_j);
- if (!pos.equals(new Pair<>(-1, -1))) {
- return pos;
- }
- }
- return new Pair<>(-1, -1); // not found
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement