따라서 처음부터 끝까지 모두 탐색하는 기법은 worst case의 경우 시간복잡도가 (O(N))이다.
하지만 이분탐색의 경우 탐색범위를 절반씩 줄여나가기 때문에 O(logN)으로 완전탐색보다 빠르다.
1. 탐색하고자 하는 배열은 이미 정렬이 되어있다.
2. left, right 값을 통해 중간값인 mid 값을 구한다.
3-1. 찾고자하는 값이 mid 위치에 존재하는 값보다 클 경우 , left를 mid 뒤로 옮긴다.
3-2. 찾고자하는 값이 mid 위치에 존재하는 값보다 작을 경우 , right를 mid 앞으로 옮긴다.
4. 다시 위의 과정을 left가 right 값보다 커질 때까지 반복한다.
- 예시
배열의 총 길이는 8이므로
left =0 , right= 7이되고 mid=3가 된다.
mid에 존재하는 값이 찾고자 하는 값인 7보다 크므로 right를 mid-1로 update 한다.
이 때 , mid에 존재하는 값보다 찾고자 하는 값인 7이 더 뒤에 있으므로 left를 mid+1로 update 한다.
마지막으로 left,right,mid 모두 같은 위치에 존재하고 드디어 찾고자 하는 7을 찾을 수 있게 되었다.
[코드]
int main(void)
{
int arr[8] = {1,3,7,8,9,15,17,21};
int target = 7;
int left = 0;
int right = 7;
int mid;
while(left <= right)
{
mid = (left+right)/2;
if(arr[mid] < target ) left = mid+1;
else if( arr[mid] > target) right = mid-1;
else return mid;
}
}
구간 합을 구할 때 사용되는 알고리즘으로 배열의 길이가 짧은 경우 이중 for문을 사용해서 구하면 되지만
배열의 길이가 길어지면 시간 초과가 발생하므로 투 포인터 알고리즘을 사용한다.
아래 코드에서 보면 N은 배열의 크기, M은 구하고자 하는 합이다.
구간의 합이 M을 만족하는 경우의 수를 구한다고 하자.
start, end 모두 배열의 첫번째부터 시작한다.
- M = sum
구간의 합이 M과 같다면 경우의 수 total에 1을 추가한다.
그리고 end를 한칸 뒤로 움직인다.
- M < sum
현재 구간의 합이 구하고자 하는 구간의 합보다 크다면 start를 1씩 증가시켜 주면서 구간의 범위를 좁혀준다.
이 때 start가 end보다 커지게 되는 경우 start, end를 같은 위치로 처리한다.
- M > sum
현재 구간의 합이 구하고자 하는 구간의 합보다 작다면 end를 한칸 뒤로 움직여 구간의 범위를 넓혀준다.
[코드]
int start =0 ;
int end =0;
int sum =arr[0];
while(start <= end && end < N)
{
if(sum < M) sum += arr[++end];
else if( sum > M)
{
sum -= arr[start++];
if( start > end && start <N){
end= start;
sum= arr[start];
}
}
else if (sum == M)
{
total++;
sum += arr[++end];
}
}
