540. Single Element in a Sorted Array(Medium)

You are given a sorted array consisting of only integers where every element appears exactly twice, except for one element which appears exactly once.

Return the single element that appears only once.

Your solution must run in O(log n) time and O(1) space.

정확히 한 번 나타나는 한 요소를 제외하고 모든 요소가 정확히 두 번 나타나는 정수로만 구성된 정렬된 배열이 제공됩니다.

한 번만 나타나는 단일 요소를 반환합니다 .

솔루션은 O(log n)시간과 O(1)공간에서 실행되어야 합니다.

배열에서 모두 2개씩 존재하는데 1개만 존재하는 원소를 찾는문제 그냥 반복문으로 세어보면 답이 나온다 하지만 문제에서 log(n) 시간복잡도 해결하라함 정렬되어있고 숫자찾기 log(n)은 이진탐색을 사용

 

일반적으로 2개씩 존재하니까 짝수번째 인덱스 x 의 값과 x+1번째인덱스의 값이 같아야한다 하지만 중간에 1번만 반복하는 원소가 있으면 그 순서가 달라짐 결국 x 번 값과 x+1 번 값을 비교해 특정구간에 원소가 있는지 찾아냄

뭔가 더 간단하게 될거같다.

class Solution:
    def singleNonDuplicate(self, t: List[int]) -> int:
        a=0
        b=len(t)-1
        if b==0:
            return t[0]
        if t[0]!=t[1]:
            return t[0]
        elif t[-2]!=t[-1]:
            return t[-1]
        while True :
            c=(a+b)//2
            if c%2==0:
                if t[c-1]==t[c]:
                    b=c
                elif t[c]==t[c+1]:
                    a=c
                else:
                    return t[c]
            else:
                if t[c-1]==t[c]:
                    a=c-1
                elif t[c]==t[c+1]:
                    b=c+1
                else:
                    return t[c]