[알고리즘] 간단한 이진탐색 구현

포인트

• 간단한 이진 탐색을 구현해보자
• 이진 탐색의 조건은? -> 정렬이 되어 있어야 한다.
• lower_bound, upper_bound 의 개념을 사용할 수 있다.

🧶문서는 항상 수정 될 수 있습니다. 비판은 환영합니다. 

c++/cpp

	#include <iostream>
	#include <algorithm>
	using namespace std;
	#define MAX 5001
	int d[MAX], n;
	bool binarySearch(int a) {
	int l = 0, r = n - 1; // 투 포인터 알고리즘으로
	while (l <= r) {
	int mid = (l + r) / 2;
	if (a == d[mid]) return true;
	else if (a > d[mid]) l = mid + 1;
	else r = mid - 1;
	}
	return false;
	}
	int main() {
	cin>>n;
	for (int i = 0; i < n; i++)
	cin >> d[i];
	sort(d, d + n); //배열 하고 벡터는 다릅니다.
	int t;
	cin >> t;
	while (t--) {
	int x;
	cin >> x;
	if (binarySearch(x)) cout << "exist" << endl;
	else cout << "not exist" << endl;
	}
	}

view raw main.cpp hosted with ❤ by GitHub

python

def binarySearch(arr, target: int) -> int:
    left = 0
    right = len(arr) - 1

    while left < right:
        mid = left + (right - left) // 2

        if mid == target:
            return target
        elif arr[mid] <= target:
            left = mid + 1
        else:
            right = mid

    return -1

 

이진 탐색에서 mid 값을 left+(left-eight)//2 로 구한 이유는?

> 자칫 발생할 수 있는 오버플로우를 예방 하기 위해서 이다. 

left + (left-right)//2 == (left+right)//2 와 논리적으로 동일하지만 left+right 는 오버플로우가 발생할 수 있다. 따라서, 이것을 해결할 필요성이 있다.