40. 탐색 (1)

배열에서 원하는 값을 찾는 방법에는 여러 방법이 있다.

대표적으로는 배열의 0번 인덱스에서부터 마지막 인덱스까지 모든 배열을 확인하는 방법이 있다.

이처럼 이번에는 다양한 탐색 알고리즘에 대해서 알아보려고 한다.

---

순차 탐색

순차 탐색은 모든 탐색 중 가장 기본적인 탐색 방법이다.

배열의 첫 인덱스의 데이터에서부터 모든 데이터를 하나씩 확인하는 방법이다.

int linearSearch(int arr[], int n, int key){
    int i;
    
    for(i=0;i<n;i++)
        if(arr[i] == key) return i;
    return -1;
}

---

이진 탐색

이진 탐색은 정렬되어 있는 배열에서 범위를 절반씩 줄여나가면서 값을 찾는 탐색 방법이다.

현재 배열의 가운데 값이 찾는 값 보다 크다면 오른쪽을 줄이고, 작다면 왼쪽을 줄여 나가면서 값을 찾는다.

int binarySearch(int arr[], int n, int key){
    int i, l = 0, r = n - 1, c;
    
    while(l <= r){
        c = (l + r) / 2;
        if(arr[c] == key) return c;
        else if(arr[c] > key) r = c-1;
        else l = c + 1;
    }
    return -1;
}