74. Search a 2D Matrix

---

문제 분석

주어진 2차원 배열은 [0][0]부터 마지막 값까지 순서대로 정렬되어 있고
해당 2차원 배열안에 target이 포함되어있다면 true, 아니면 false를 리턴하는 문제

---

풀이 과정

1. 2차원 배열 안에 1차원 배열을 탐색할 이분 탐색 반복문
2. 1차원 배열 안에 값을 탐색할 이분 탐색 반복문

1번 반복문 안에 2번 반복문을 두고 탐색을 한다.
보통의 이분 탐색처럼 탐색한다.

target과 값이 같다면 true를 리턴한다.
target이 크다면 값이 모자라다는 뜻이기 때문에 시작 인덱스를 올려주고
target이 작다면 값이 넘친다는 뜻이기 때문에 마지막 인덱스를 내려주어서
중간 인덱스를 수정해가며 값을 찾는다.

시작인덱스가 마지막인덱스보다 커지면 반복문을 종료하는데 이때 무조건 false를 리턴한다.

---

나의 생각

작은 문제부터 해결하면서 접근하니 크게 어렵지 않게 풀 수 있었다.
1차원 배열을 이분 탐색하는 로직을 먼저 구현하고
해당 결과를 바탕으로 2차원 배열을 이분 탐색하니 풀 수 있었다.

---

코드

    public boolean searchMatrix(int[][] matrix, int target) {
        int arrStartIndex = 0;
        int arrEndIndex = matrix.length - 1;

        while (arrStartIndex <= arrEndIndex) {
            int arrMidIndex = (arrStartIndex + arrEndIndex) / 2;
            int[] arr = matrix[arrMidIndex];

            int startIndex = 0;
            int endIndex = arr.length - 1;
            int midIndex = 0;

            while (startIndex <= endIndex) {
                midIndex = (startIndex + endIndex) / 2;

                int check = arr[midIndex];

                if (check == target) return true;
                if (check < target) startIndex = midIndex + 1;
                if (check > target) endIndex = midIndex - 1;
            }

            int check = arr[midIndex];

            if (check < target) arrStartIndex = arrMidIndex + 1;
            if (check > target) arrEndIndex = arrMidIndex - 1;
        }

        return false;
    }