Binary Search

📝 간단한 개념정리

• 이진 탐색 : 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘. 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해 원하는 데이터를 찾는 것이 이진 탐색 과정이다.

• 시간복잡도 : O(logN)

👆🏻 Binary Search

• Python으로 구현

def binary_search(arr, target):
    low, high = 0, len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] > target:
            high = mid - 1
        if arr[mid] == target:
            return mid
        if arr[mid] < target:
            low = mid + 1
    return -1


arr = ["A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "N", "O", "P"]
target = "G"

result = binary_search(arr, target)
print(result)

결과값
6

• Javascript로 구현

function binary_search(arr, target){
    let low = 0,
        high = arr.length - 1;
    while(low <= high){
        let mid = parseInt((low + high) / 2); 
        if (arr[mid] > target){
            high = mid - 1;
        } if (arr[mid] === target){
            return mid;
        } if (arr[mid] < target) {
            low = mid + 1;
        }
    }
    return -1;
}


let arr = ["A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "N", "O", "P"]
const target = "G"

let result = binary_search(arr, target)
console.log(result)

결과값
6

🤲🏻 차이점

• 참고로 Python에는 bisect라는 라이브러리가 있어서 binary search를 쉽게 사용할 수 있다!

  • 참고코드

  from bisect import bisect_left, bisect_right
  
  		a = ["A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "N", "O", "P"]
  		x = "G"
  
  		print(bisect_left(a, x))
  		print(bisect_right(a, x))

  결과값
  6
  7

• while문, if문의 형태가 조금 다름.

참고자료

• Javascript if문 - https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Statements/if...else
• Python에서는 // 연산자는 나누기의 몫을 결과값으로 나온다. 하지만 Javascript에서는 //는 주석이기 때문에 parseInt(피연산자/피연산자)를 통해 나누기의 몫을 얻을 수 있음. 참고로 나누기의 나머지인 % 연산자는 Python과 Javascript 모두 동일함.
• ==와 === 차이점 - https://hianna.tistory.com/376?category=764998