[탐색] 👍👎이진 탐색(binary search) + 🔧변형

이진탐색(binary search) 알고리즘 =병뚜껑 게임👍👎

탐색공간을 반으로 나누고 두 부분 중 한 부분만 탐색하는 일을 반복하는 알고리즘(=병뚜껑 게임👍👎)

∎ 정렬된 데이터에만 사용

∎ 정렬된 배열 A🧱에서 목푯값 V🚩를 효율적으로 탐색🧐하는 데 사용

∎ 배열이 '오름차순🧱'으로 정렬 👉 " i<j인 모든 인덱스 쌍 i, j에 대해 A[i]=<A[j] "

∎ 탐색 공간의 양쪽 경계(상계, 하계)를 추적해 중간값과 목푝값 비교를 반복함🔁. (Until🚩 중간값=목푯값)

∎ 중간값만을 확인 👉 상계와 하계 인덱스 값은 확인❌

∎ [ A(하계) ≦ v ≦ A(상계) ]

😈 상계 인덱스: 현재 탐색중인 공간에 있는 요소 가운데 인덱스가 가장 큰 요소

😈 중간인덱스: (상계 인덱스 + 하계 인덱스) ÷ 2

😈 하계 인덱스: 현재 탐색중인 공간에 있는 요소 가운데 인덱스가 가장 작은 요소

Binary search (target value=12)

∎ 탐색 과정

🤓🔎. 중간값 < 목푯값
A[중간인덱스]<v 👉 목푯값이 중간보다 뒤⏩
하계 = 중간 + 1 👉 탐색공간 반🪓으로 나.가.리

🤓🔎. 중간값 > 목푯값
A[중간인덱스]>v 목푯값이 중간보다 앞⏪
상계 = 중간 - 1 👉 탐색공간을 반🪓으로 나.가.리

🤓🔎. 중간값 = 목푯값
A[중간인덱스] = v 👉 탐색 끝 ❗

🤓🔎. 배열에 목푯값❌
탐색 반복 👉 상계와 하계가 점점 가까워져서 더는 확인할 값이 없어지는 순간 발생.
상계 < 하계 👉 탐색 STOP❗
탐색 중 상계 인덱스 < 하계 인덱스 👉 배열 내 목푯값❌

∎ 이진 탐색의 장점💗

😇 중간값과 목푝값 비교를 반복함으로서 유효 탐색 공간 줄임.

😇 데이터의 구조 정보를 활용해 탐색의 효율성을 높임.

*효율적 알고리즘 👉 정보🤍

🤍 데이터의 정렬 기준을 알고 있어야 함. (for 탐색의 효율성)

🤍 But 현재 정렬된 기준이 탐색 기준과 다르다면 이진 탐색❌
 cf. 지출기입장
  언제 어디서 얼마를 썼는지 번호 오름차순으로 정리된 지출기입장 있음. 
  지출의 순서 탐색 👉 이진 탐색⭕ 
  지출금액이나 지출출처의 순서 탐색 👉 이진 탐색❌  👉 완전 탐색

이진 탐색 알고리즘 변형

처음 보는 문제 or 변형된 문제 👉 알고리즘 원리 이해🎓 + 조정🎰

∎ 데이터의 구조를 활용해 탐색 공간을 계속 절반으로 줄여나가는 이진 탐색의 기본 발상을 이해

∎ 기본 발상을 통해 직관적으로 이진 탐색을 조정하여 탐색문제 해결
cf. 원형 배열 탐색문제👍👎, 좋아하는 커피의 적정 온도 찾기👍👎, 병뚜껑 게임👍👎

다음 포스팅💌 👉 역추적 탐색 + 너비 우선 탐색 + 깊이 우선 탐색