728x90
데이터 탐색 방법
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형
728x90
