Linear, Binary Search

Linear Search

List 내에서 순서대로 원하는 값을 찾는다.

List 안에 값이 많다면, 그만큼 시간이 오래 걸린다.

ex) 100만개가 있고, 우리가 찾는 값이 마지막에 있다면 100만번 검사해야한다

효과

O(n)

Binary Search

Concept

여기서 Binary는 0과 1을 의미하는게 아니라 반으로 쪼갠다는 의미다

전재 조건은 List가 정렬이 되어 있어야 한다.

정렬이 안되어 있으면 정렬하는 시간도 고려야 해야 하기때문에 상황에 맞춰서 사용해야 한다.

List가 엄청 나게 크고, 그 안에 값을 찾아야 하는 상황이 많다면 Binary Search는 꼭 필요 하다

동작 과정

1. List의 처음과 끝 위치를 구한다 (first, last)
2. 중간 위치를 구한다 (first + last / 2)
3. 중간값과 우리가 찾는 값을 비교한다
   
   3-1. 같다면, 성공
   
   3-2. 작으면, 첫번째 반쪽으로 다시 binary search를 수행한다 (recursive call)
   
   3-2. 작으면, 두번째 반쪽으로 다시 binary search를 수행한다 (recursive call)
4. 성공하면 찾는 값을 주고 검색 로직 끝
5. 못찾으면 에러 또는 기본 값 노출하고 로직 끝

효과

O(log n)

• Big O Notation 에서는 상수 값은 제외

• n을 2로 나눠서 1에 가장 근접할 때 까지 나눈 수
• List 내에 1만개 요소가 있을 땐 최악의 경우 14번만 검색 하면 되어 엄청 효율적이다

graph¹