🖍️ includes 구현하기

대규모 배열의 경우 배열 요소의 존재 여부를 확인하기 위한
최적의 성능을 갖춘 알고리즘을 찾고 있다면
이진 검색이나 HashSet(JavaScript Set 객체) 사용과 같은 대안을 고려 가능
알고리즘 선택은 데이터의 특성에 따라 달라짐

이진 탐색 (정렬된 배열)

• 정렬된 배열에 대해 매우 효율적 (includes 보다 빠름)
• O(log n) 성능

const binary_search = (arr, e) => {
  let start = 0;
  let end = arr.length - 1;
  
  while (start <= end) {
  	let mid = Math.floor((start + end) / 2);
    
    // 찾았을 때
    if (arr[mid] === e) {
    	return true; 
    }
    
    if (arr[mid] < 2) {
    	start = mid + 1;
    } else {
    	end = mid - 1;
    }
  }
  // 못 찾았을 때
  return false;
}  

HashSet (정렬되지 않은 배열)

• 배열이 정렬되지 않고 여러 조회 필요한 경우 배열을 Set 으로 변환
• Set 은 조회에 대해 O(1) 성능 제공

const isElementInSet = (arr, e) => {
   const set = new Set(arr)
   return set.has(e);
}

정렬된 배열은 이진 검색 사용
특히 여러조회가 필요한 경우 정렬되지 않은 배열은 HashSet 으로 변환
작거나 중간 크기의 배열에 대한 단일 조회의 경우 includes 선택

📢 이진탐색

• 정렬된 배열
• 임의 액세스
  • 배열과 같이 빠른 무작위 액세스를 허용하는 데이터 구조에서 가장 효과적
  • 특정 인덱스의 요소에 빠르게 액세스해야 하기 때문
  • 임의 액세스가 느린 연결 목록과 같은 구조에서는 이진 검색이 성능 이점을 잃음
• 결정론적 순서
  • 요소가 배열의 다른 요소보다 크거나 작거나 같은지 여부를 확인하는 명확
• 중복 없음 (선택)
  • 이진 검색은 중복이 포함된 배열에서 작동할 수 있지만 중복을 처리하려면 추가 논리가 필요