홀수 셔플링(이진 검색 변형)

문제 설명 -

In a sorted array, the odd indices are divided in two parts. Elements on left are swapped with elements on right. We have to search for index of a given number in that array.

예시 -
""
A = [1, 6, 3, 4, 5, 2]
B = 5
답변 = 4
""

찾기 = B의 인덱스.
접근 방식 - logN에서 해결해야 합니다. 따라서 이진 검색을 사용해야 합니다. 그러나 정렬된 배열에만 적용됩니다.
따라서 정렬된 짝수 인덱스에 대해 이진 검색을 적용하고 B 또는 B에 가장 가까운 숫자를 찾으려고 합니다.

사례 1: B를 찾을 수 있습니다.
인덱스를 반환합니다.
사례 2: B를 찾을 수 없습니다.
따라서 결과 옆에 있는 숫자를 찾습니다. 이것은 B가 정렬된 배열에 있어야 하는 위치입니다. 그래서, 그것이 B와 같으면 우리는 다른 것을 반환합니다. 우리가 찾은 숫자는 B와 교환된 숫자입니다.to_find = A[ans + 1] 그래서 우리는 짝수 인덱스에 대해 이진 검색을 시도하고 to_find를 찾습니다.
다시, A[ans] = to_find이면 반환하고, 그렇지 않으면 + 1 인덱스를 확인합니다.
해결책

class Solution:
    # @param A : list of integers
    # @param B : integer
    # @return an integer
    def solve(self, A, B):
        lo = 0
        hi = (len(A)-1)//2
        ans = float('-inf')
        ans_idx = None
        # first search over all even indices
        while lo <= hi:
            mid = (lo + hi)//2
            if A[mid * 2] == B:
                return mid * 2
            else:
                if A[mid * 2] > B:
                    hi = mid - 1
                else:
                    ans = max(ans, A[mid * 2])
                    ans_idx = mid * 2
                    lo = mid + 1
        if A[ans_idx + 1] == B:
            return ans_idx + 1
        to_find = A[ans_idx + 1] # this is the number that was swapped
        # in binary search try to find, this smaller or larger number.
        lo = 0
        hi = (len(A)-1)//2
        ans = float('-inf')
        ans_idx = None
        # first search over all even indices
        while lo <= hi:
            mid = (lo + hi)//2
            if A[mid * 2] == to_find:
                return mid * 2
            else:
                if A[mid * 2] > to_find:
                    hi = mid - 1
                else:
                    ans = max(ans, A[mid * 2])
                    ans_idx = mid * 2
                    lo = mid + 1
        # print('ans', ans_idx, to_find, ans)
        if A[ans_idx + 1] == B:
            return ans_idx + 1
        return - 1