100칸짜리 배열 두개가 있고, 값은 임의로 정할게.

1. 각 배열의 중간값부터 탐색

arr1[50] == 23, arr2[50] == 73

그럼 arr2의 인덱스를 25로 하거나, arr1의 인덱스를 75로 두고 다시 탐색. 여기선 작은쪽의 인덱스를 높여보겠음

arr1[75] == 78, arr2[50] == 73

다음은

arr[75] == 78, arr2[75] == 87

arr[87] == 86, arr2[75] == 87

arr[88] == 87, arr2[75] == 87

이런식.


근데 논의하던 문제는 특정 인덱스 이전의 요소들이 전부 같음

예컨대 arr1 = {0, 1, 2, 4, 5, 7, 8 ....}, arr2 = {0, 1, 2, 4, 6, 9, 10 ...} 처럼, 4 이후엔 겹치는 숫자가 절대 없음

그렇다면 앞서 중복값을 찾았던 것 처럼, 4를 찾으면 됨


앞의 케이스와 차이점은 공통 값을 찾았다고 탐색을 중지하는 것이 아니다. 라는 것

무조건 뒤의 인덱스를 탐색해봐야한다.

그러기 위해선 각 배열에서 최대 공통 값의 바로 다음 인덱스가 서로 다른값인지 검사해야함.

이 과정도 물론 이진탐색으로 가능함


아무튼 O(logN)이라는 뜻