이분탐색 알고리즘의 경우 구현이 단순한 편입니다.
그래도 눈 여겨볼 부분이 있다면 찾는 값이 존재할 때와 존재하지 않을 때 입니다.
Collections.binarySearch
일단 java 에서 Collections.binarySearch 는 원하는 값 즉 key 가 존재할 땐 양수의 인덱스를 key 가 존재하지 않을 땐 음수의 (인덱스 + 1)을 반환합니다.
이는 기본적으로 key 의 존재여부를 +, - 부호로 구분하는데 찾아낸 key 의 인덱스 0와 key 가 존재하지 않아 추가되기에 적합한 인덱스 0이 구분되지 않기 때문입니다.
따라서 key 가 존재하지 않을 때를 1-based index 처럼 다루어 해결하는 것입니다.
그래서 사용 시엔 - 임을 확인하고 - 라면 0-based index 로 변형하는 과정을 가져야합니다.
Collections 는 java 의 collection 들을 다루는 클래스입니다. binarySearch 같은 메소드 또한 collection 을 인자로 받아 범용적으로 사용할 수 있는데 단순히 ArrayList 뿐만 아니라 LinkedList 를 받아 사용할 수도 있습니다.
내부에선 임의 접근이 가능한지 여부에 따라 분기를 하는데 이 경우 조회 시 임의접근이 불가해 순차접근이 발생하고 기존에 기대하던 시간 성능은 사실상 힘듭니다. (기존 시간복잡도가 O(lgn)이였으면 순차접근 시 O(nlgn) 을 예상할 수 있습니다.
그외 재밌었던건 익숙치 않았던 >>> 연산이였습니다.
이분탐색의 경우 low, high 인덱스를 통해 중간값을 구해야하는데 보통의 경우 나누기 연산으로 충분합니다.
Unsigned right shift
>>> (Unsigned right shift)연산은 부호비트를 포함해 전체를 비트연산하는 연산자인데 오버플로우가 일어날 수 있는 연산을 조금 방지할 수 있습니다. 관련 정보
int a = -8; // 이진수: 11111111 11111111 11111111 11111000 (32비트)
int result = a >>> 2; // 이진수: 00111111 11111111 11111111 11111110
System.out.println(result); // 결과: 1073741822손으로 과정을 그려보니 더 좋았다.
개인적으로는 이분탐색에 대해 조금 더 깊게 생각할 수 있었습니다.
이분탐색이 진행됨에 따라 검색 구간이 더욱 찾는 값과 가까워짐을 손으로 그려가며 여러 케이스를 따져봤는데 꽤 좋았습니다.
이분탐색 이전에 투 포인터 고려하기
이분탐색은 O(lgn) 의 시간복잡도를 가집니다. 그 전제에는 정렬이 되어야하는데 따라서 정렬되지 않은 자료구조에서 이분탐색은 O(nlgn) 의 시간복잡도를 가집니다.
따라서 이분탐색으로 값을 찾아야할 때 투 포인터로 먼저 접근할 순 없는지 고려해봅시다. 투 포인터의 경우엔 O(n) 의 시간복잡도를 가져 상황에 따라 이분탐색보다 뛰어난 성능을 기대할 수 있습니다.
