이진탐색 알고리즘

21/10/27 : 내용 수정 및 js코드 추가

순차 탐색

먼저 순차 탐색에 대해 알아본다.

특정 데이터를 탐색하는데 앞에서부터 데이터를 하나씩 차례로 확인하는 방법이다.
자료에서 데이터를 찾을 때 가장 보편적으로 사용한다.

시간만 충분하다면 항상 원하는 데이터를 찾을 수 있다.

# python
for i in range(n):
    if array[i] == target:
        return i

// javascript
for (let i in arr) {
 if (arr[i] === target) {
   return i
 }
}

시간 복잡도는 O(N)이다. (처음부터 순차적으로 탐색하기 때문)

원하는 데이터를 찾는데, 만약 자료가 정렬되어있다면 어떻게 될까?
만약, 찾으려는 데이터가 자료의 평균보다 크다면, 뒤에서 부터 찾기 시작할 것이다.

이처럼, 데이터가 정렬이 되어있다면, 탐색에 이점을 갖는다.

이진 탐색

자료의 중간 부분과 찾는 데이터를 비교하고,
찾는 데이터가 더 작다면 앞, 크다면 뒤와 다시 비교 하는 탐색 알고리즘이다.

때문에, 이진탐색을 하기 위해서는 반드시 정렬되어 있어야한다

진행 과정

중간점을 선택하고, 찾는 데이터와 비교하여 범위를 줄여나간다.
O(logN)의 시간 복잡도를 갖는다. (한번 시행마다 절반 씩 줄어듦)

컴퓨터 공학에서 밑이 생략된 log는 2의 밑을 가진다.

재귀 혹은 반복문 2가지 방법으로 이진탐색을 구현할 수 있다. (사실 대부분이 이렇다)

구현 방법

재귀

# python
def binary_search(arr,target,start,end):
    if start>end: return None

    mid = (start+end)//2

    if arr[mid] == target:
        return mid
  
    elif arr[mid] > target:
        return binary_search(arr,target,start,mid-1)
  
    else:
        return binary_search(arr,target,mid+1,end)

arr = [2,4,5,6,9,10]
result = binary_search(arr,4,0,len(arr)-1)

print(result) # 1

// javascript
const binarySearch = (arr, target, start, end) => {
  if (start > end) return null;

  const mid = Math.floor((start+end) /2)
  const pivot = arr[mid];

  if (target === pivot) {
    return mid;
  }
  else if (target > pivot) {
    return binarySearch(arr,target,mid+1, end);
  }
  else {
    return binarySearch(arr,target, start,mid-1);
  }
}

const arr = [1,3,5,6,7,8,9,10];
const target = 8;

console.log(binarySearch(arr,target,0,arr.length-1)); // 6

반복문

def binary_search2(arr,target,start,end):
  while start <= end:
    mid = (start+end)//2
    if arr[mid] == target:
      return mid

    elif arr[mid] > target:
      end = mid-1
    
    else:
      start = mid+1

  return None

arr2 = [2,4,5,6,9,10]
result = binary_search(arr2,9,0,len(arr2)-1)
print(result) # 4

탐색 범위가 큰 상황에서 자료가 정렬되어 있다면, 이진 탐색을 시도해보자.