[이진탐색] binary Search - JS, Python

이진탐색 알고리즘

• 이진탐색의 전처리 과정은 오름차순 정렬이다
• 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘
• 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교하는 알고리즘
• 반으로 쪼개면서 탐색하기

1. 정렬된 리스트를 준비한다

2. idx 0부분을 start, idx 마지막 부분을 end, (start + end) // 2를 mid로 설정

3. array[mid]값이 target보다 크면 end를 mid-1지점으로 바꾼다 + mid도 다시 설정

4. array[mid]값이 target보다 작으면 start를 mid+1지점으로 바꾼다 + mid도 다시 설정

5. start가 end보다 클때까지 반복한다 

6. 반복했음에도 값이 없으면 None을 반환하고, array[mid]가 target과 같으면 mid + 1값(target값의 index)을 출력 

Big O

BEST : O(logN)

WORST : O(logN)

 

단계별로 확인해야 하는 데이터 갯수가 반씩 줄어든다, 즉 단계마다 2로 나누는것과 동일

 

 

장점

• 선형탐색과 비교했을 때 탐색시간이 빠르다 (선형탐색 시간 복잡도 O(N))

단점

• 정렬된 리스트에서만 사용할 수 있다

 

Python 코드

반복문 구현

# 반복문 구현
def binaray_search(array, target, start, end):
    while start <= end:
        mid = (start + end) // 2
        # 찾은 경우 중간점 인덱스 반환
        if array[mid] == target:
            return mid
        elif array[mid] > target:
            end = mid - 1
        else:
            start = mid + 1
    return None



n, target = map(int, input().split())
array = list(map(int, input().split()))

# print(n, target, array)

# 이진탐색 수행 결과 출력
result = binaray_search(array, target, 0, n-1)
if result == None:
    print('원소 존재 안함')
else:
    print(result + 1) # 몇번째에 존재하는지 반환

 

재귀 구현

# 재귀구현
def binaray_search(array, target, start, end):
    # target값이 없는 경우
    if start > end:
        return None
    mid = (start + end) // 2
    # 찾은 경우 중간점 인덱스 반환
    if array[mid] == target:
        # mid idx반환
        return mid
    elif array[mid] > target: # 중간값이 target값보다 큰 경우(target의 오른쪽)
        # 중간값의 왼쪽 확인
        return binaray_search(array, target, start, mid-1)
    else: # 중간값이 target보다 작은 경우
        # 중간값의 오른쪽 확인
        return binaray_search(array, target, mid+1, end)
        
        
n, target = map(int, input().split())
array = list(map(int, input().split()))

# print(n, target, array)

# 이진탐색 수행 결과 출력
result = binaray_search(array, target, 0, n-1)
if result == None:
    print('원소 존재 안함')
else:
    print(result + 1) # 몇번째에 존재하는지 반환

 

JS 코드

const binary_search = function(array, target, start, end) {
  
  while (start <= end) {
    let mid = parseInt((start + end)/2)
    // console.log(mid)
    if (array[mid] == target) {
      return mid
    } 
    else if (array[mid] > target) {
      end = mid - 1
    } else {
      start = mid + 1
    }
  }
  return None
}


let N = 10
let target = 7
let array = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]

const result = binary_search(array, target, 0, array.length - 1)
console.log(result + 1)