algorithm/theory

이분(이진) 탐색

qkqhxla1 2016. 11. 10. 10:29
기초적이지만 그래도 정리...

파이썬
# -*- encoding: cp949 -*-
def binary_search(l, data):
    low,high = 0,len(l)
    while low<high:
        bl,bh = low,high
        mid = (low+high)/2
        if l[mid] == data:
            return True
        elif l[mid] > data:
            high = mid
        else:
            low = mid
        if bl==low and bh==high:
            return False
    return False

a=sorted(map(int,raw_input().split()))
print binary_search(a, input())

C++

#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <string>
using namespace std;
 
bool binary_search(int l[100], int data)
{
	int low = 0,high = 100;
	while(low < high)
	{
		int bl = low, bh = high;
		int mid = (low+high)/2;
		if(l[mid]==data)
			return true;
		else if(l[mid] > data)
			high = mid;
		else
			low = mid;
		if(bl==low && bh==high)
			return false;
	}
	return false;
}

int main() 
{
	int a[100], input;
	scanf("%d",&input);
	for(int i=0;i<100;i++) //0~99
		a[i] = i;
	cout<<binary_search(a,input)<<"\n";

    return 0;
}