[바미] Search algorithm - Binary search 구현하기.

바이너리 서치는 정렬된 배열에서 특정 값을 찾는 알고리즘입니다. 

코드

function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;

  while (left <= right) {
    let mid = Math.floor((left + right) / 2);

    if (arr[mid] === target) {
      return mid;
    } else if (arr[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }

  return -1;
}

---

코드 설명

위의 코드에서 arr은 정렬된 배열이며 target은 찾고자 하는 값입니다. 변수 left와 right는 각각 배열의 가장 왼쪽과 가장 오른쪽 인덱스를 나타냅니다. 그리고 while 루프를 돌면서 left와 right가 서로 교차할 때까지 다음을 반복합니다.

1. 중간 인덱스 mid를 계산합니다.
2. arr[mid]가 target과 같으면 mid를 반환합니다.
3. arr[mid]가 target보다 작으면 left를 mid + 1로 갱신합니다.
4. arr[mid]가 target보다 크면 right를 mid - 1로 갱신합니다.

반복문을 빠져나온 경우에는 target이 배열에 없으므로 -1을 반환합니다.

코드 실행

다음과 같이 사용할 수 있습니다.

const arr = [1, 2, 3, 4, 5, 6, 7];
const target = 3;
const index = binarySearch(arr, target);
console.log(index); // 2

위의 코드는 arr 배열에서 target 값인 3을 찾아서 해당 인덱스인 2를 반환합니다.