이진 탐색은 주어진 배열 A의 가운데 요소 (정수)를 탐색하는 키 요소랑 비교하고 배열 A를 왼쪽 오른쪽 하위배열들로 나눈다. 물론 가운데 요소가 키 요소보다 작으면 오른쪽 하위 배열에서 탐색을 시작하고 키 요소보다 크면 왼쪽 하위 배열에서 탐색을 시작한다. 이런 식으로 반복적으로 배열 A가 왼쪽/오른쪽 하위 배열들로 나뉘어진다 키 요소가 발견 되거나 배열 A가 더이상 나뉘어질 수 없을 때 까지. 여기서 전 글에 계시한 순차 탐색 (Linear Search)과 이진 탐색의 차이점을 들어난다. 순차 탐색은 배열 A가 정렬 되어있지 않은 상태로도 탐색이 가능하지만 이진 탐색의 조건은 배열 A가 이미 정렬되어야 있는 상태여야 한다. 안그러면 있는 요소를 제대로 못 찾을 수도 있다. 비주얼을 아래에 첨부하겠다...

기본 탐색 알고리즘 중 하나다. 말 그대로 배열 A의 모든 소요들을 차례대로 (왼쪽부터 오른쪽)으로 탐색을 한다. 정렬되지 않아도 된 배열도 탐색 가능하다. 추가 설명이 필요없어서 바로 비주얼을 아래에 첨부하겠다. 의사코드 마저 되게 간단하다. 특별한 메서드는 필요없고 네이브로 구현했다. Linear-Search(A, n, T) for i = 0 to n - 1 do if A[i] = T then return i i = i + 1 if i = n then return false 시간 복잡도는 그냥 간단한 O(n)이다 (nested for loop이 없어서). 공간 복잡도도 역시 O(1)이다. 아래 레포지토리에 순차 탐색 프로그램을 완성하였다. 다른 알고리즘들에 비해 매우 간다나고 짧지만 그래도 참고하기엔..