[Algorithm] 이분 탐색

  이분 탐색  

리스트 내에서 데이터를 매우 빠르게 탐색하는 알고리즘이다.배열의 원소가 정렬되어있어야만 사용할 수 있다.

---

 

  사용하는 상황  

1) 특정 배열 안에 원소 x가 존재하는지 확인해야할 때

2) x이하, 또는 x이상의 원소가 몇 개 존재하는지 확인해야할 때

3) x와 가장 가까운 원소가 무엇인지 확인해야할 때

---

  코딩테스트에서의 사용 상황  

탐색 범위가 큰 상황에서 사용해라!1) 탐색 범위가 2000만을 넘어가는 상황2) 처리해야할 데이터의 개수나, 값이 1000만 단위 이상으로 넘어가는 상황-> 이진탐색과 같이 O(log N)의 속도를 갖는 알고리즘으로 처리해야함을 기억해야한다.

---

  알고리즘  

1. 탐색하고자 하는 배열을 오름차순 정렬한다 array.sorted()
2. start, end를 변수에 저장한다. 
    a. start와 end의 중간 값을 계산한다.
3. 중간 값이 찾고자 하는 값과 동일한지 확인한다.
    a. 동일하다면 mid를 반환한다.
    b. 중간 값 > target 이라면, end = mid - 1로 설정한다.
    c. 중간 값 < target 이라면, start = mid + 1로 설정한다.
4. start <= end 일 때까지 반복문을 수행한다.

---

  Key point!  

📍구하려는 값이 무엇인지 반드시 확인하자!

📍반복문의 조건과, 반환해야하는 값을 확실히 짚고 넘어가자. (상황에 따라 다를 수 있다)

---

  관련 문제  

1) 특정 배열 안에 원소 x가 존재하는지 확인해야할 때
     [부품 찾기]

2) x이하, 또는 x이상의 원소가 몇 개 존재하는지 확인해야할 때

3) x와 가장 가까운 원소가 무엇인지 확인해야할 때

 

출처 | 이것이 코딩테스트다 (나동빈)