BS : Binary Search 구현하기

낭만개발자·2022년 3월 20일
0

알고리즘

목록 보기
8/20

binary search, 이진 탐색을 js로 구현해보겠다.
이진탐색은 정렬된 배열을 search하는 알고리즘이다.
이진탐색은 간단히 설명하자면, 3 pointer 즉, leftIndex, midIndex, rightIndex 3가지 포인터를 가지고 구현을 한다.
1. while문을 활용해 반복문을 구성한다.
2. 처음에 배열 숫자 중 가운데 값을 찾고 중간값을 midIndex 포인터에 담는다.
3. 찾으려는 target 숫자와 midIndex 변수의 숫자를 비교한다.
4-1. 만약 target < midIndex 라면, midIndex에서 -1 를 해주고 rightIndex에 할당해준다.
4-2. 만약 target > midIndex 면, midIndex에서 +1를 해주고
leftIndex에 할당해준다
4-3 만약 target === midIndex 면, 해당 인덱스를 return 해준다.

while문 반복이 되면서 찾게 된다.

코드

let root = [1,2,4,6,7,9,10]; 
let target = 10;

function binarySearch(root, target){
  //3가지 포인트 정리
    let leftIdx=0, rightIdx=root.length -1, midIdx =0;

  	
    while(leftIdx <= rightIdx){
      	//overflow 방지 safe code. = (left+right)/2
        midIdx = leftIdx + (rightIdx - leftIdx)/2;
        
      if(target === root[midIdx]){
       return midIdx;
      } else if(target < root[midIdx]){
        rightIdx = midIdx - 1; //target이 midIdx 값보다 작으면 rightIdx를 조정해준다
      } else if(target > root[midIdx]){
        leftIdx = midIdx + 1; //target이 midIdx 값보다 크면 leftIdx를 조정해준다
      }
    }
 return 0;   
}
console.log(binarySearch(root, target));
profile
낭만닥터와 슬의를 보고 저런 개발자가 되어야 겠다고 꿈꿔봅니다.

0개의 댓글