세미나 - 이분탐색

데이터 탐색 방법 

1) 순차탐색 : 순차적으로 하나씩 확인하여 탐색

2) 이분탐색 : 범위를 반씩 좁혀가면서 데이터 빠르게 탐색

 

왜 필요한가?

일반적인 O(n)탐색이 불가능할때

값을 찾는 시간이 굉장히 오래걸릴때!

이분탐색 알고리즘 : 데이터의 범위를 추측해서 탐색

 

<배열을 이용할때>

- 배열(벡터 )정렬

- left(최소), right(최대)를 지정

- mid = (left+right)/2

- mid와 찾는값 (key)비교

mid < key 라면, left = mid +1로 갱신

mid >key라면, right = mid-1로 갱신

 

-반복문 /재귀 종료 조건

mid ==key: key값을 찾은경우

left>right :배열에 key값이 존재하지 않는경우

 

 

 

<값 자체>

1~2^63 : left : right

mid 값의 제곱이 찾는 값이라면?

이런식으로

수가 나열이 되어있다고 생각하면 요런식으로 생각해야함

무조건 2^63인건아니고 저건 예시임

mid ^2 <찾는값

이라면 left = mid + 1 해줘야함

mid ^2 > 찾는값

이라면 right = mid -1 으로 범위를 줄여줘야~

 

 

 

 

2^31 까지가 int형