[Algorithm] 이진 탐색 (이분 탐색, Binary Search) 코드와 시간 복잡도

인트로 이진 탐색이란 정렬된 배열에서 특정 값을 찾는 탐색 알고리즘이다. 이진 탐색은 배열의 중간을 기준으로 데이터를 탐색하기 때문에 반드시 데이터가 정렬된 상태로 존재해야 한다. 이진 탐색의 시간 복잡도는 O(logN)으로 배열을 전수 조사하는 O(N)에 비하면 상대적으로 빠른 탐색 알고리즘에 속한다. O(logN)만에 값을 찾을 수 있는 이유는 중간을 기준으로 탐색 대상을 절반씩 줄여나가기 때문이다. 본 포스팅 말미에 코드와 시간 복잡도 계산법을 상세히 적어놨으니 참고하시길 바랍니다. 이진 탐색 : 개념 이진 탐색은 내가 찾고자 하는 값이 정렬된 배열의 중간 값보다 크면 중간값을 포함한 하위 값들은 탐색 대상에서 제외된다. 반대로 찾고자 하는 값이 배열의 중간 값보다 작으면 중간 값을 포함한 상위 값..