알고리즘/개념

[JS] 이진 탐색(이분 탐색)

이진 탐색 알고리즘(Binary Search Algorithm)은 이미 정렬되어 있는 배열에서 탐색 범위를 두 부분 리스트로 나눠 절반씩 좁혀가 필요한 부분에서만 탐색하도록 제한하여 원하는 값을 찾는 알고리즘입니다. 예를 들어 1부터 10까지의 배열에서 3을 찾는다면 찾는 배열의 중간인 5를 기준으로 대소를 비교하고 3은 5보다 작기 때문에 두 부분 나눈 리스트에서 5 이상은 탐색범위에서 제외시키고 5 이하의 부분에서 다시 탐색하게 되는 방식입니다. 이진 탐색은 정렬되어 있는 배열이 필요로 하며 각 left, right, mid의 변수가 필요하게 됩니다. left은 왼쪽의 끝 인덱스를 뜻하며 right는 오른쪽의 끝 인덱스를 뜻하고 left와 right의 사이는 탐색범위가 됩니다. 변수명은 (low, h..