Linear Search(선형검색), Binary Search(이진검색)

선형검색, 이진검색이란?

---

선형 검색(Linear Search)

다른이름으로 순차 검색(Sequential Search) 이라고도 하는 선형검색에 대하여 먼저 알아보겠습니다.

선형 검색은 데이터가 모인 집합(배열, LinkedList 등)의 처음부터 끝까지 하나씩 순서대로 비교하며 원하는 값을 찾아내는 알고리즘입니다.

쉽게 말해 index가 0부터 100까지 있다고 한다면,

찾고자하는 값이 어느 인덱스에 있는지 모르니! 인덱스 하나하나를 다 열어보면서 찾고자 하는 값이

해당인덱스를 열어봤을때 일치할때 까지 반복을 한다고 생각하면 됩니다.

즉, index 0 ~ 100 까지 반복 (100번 반복) for문으로 100번 회전하게 만들고 한번 회전할때마다 그 값이 일치하는지 알아보면 되겠죠???

 

 

 

코드:

---

int LinearSearch(int arr[], int size, int find)
{
    for(int i = 0; i < size; i++)
        if(arr[i] == find) //arr이라는 배열에서 target을 찾는다.
            return i; //찾으면 해당 방번호를 리턴
    return -1; //못찾으면 -1을 리턴
}

• 배열이 특정한 규칙으로 정렬이 되있지 않아도 어느 배열에서나 사용가능 합니다!
• 데이터양이 증가함에 따라 시간복잡도 비례해서 증가합니다! (시간복잡도 0(n) )worst case (최악의 상황) 인 100번째에 위치하고 있다면 100번을 반복해야 합니다!여기서 시간 복잡도가 뭔지 궁금하시다면? 쉽게 말해서 저희가 각자 사용하는 컴퓨터의 cpu, 그래픽카드, ram의 용량에 따라결과까지 도달하는데 몇 단계가 소요됬나를 기준으로 잡습니다….선형검색은 최대 10번을 반복해야지 데이터를 찾을 수 있다 (10 단계)이렇게 생각하면 편하죠??

  ---

• 이진검색은 최대 4번을 반복해야지 데이터를 찾을 수 있다 (4단계)
• Ex) 데이터가 10개가 있을때 원하는 데이터를 찾고자 한다.
• 속도, 성능 차이가 다르기 때문에 프로그래밍에서는 시간(몇분 몇초) 를 기준으로 성능을 평가 하는게 아니라
• 그렇다면 100만개의 데이터가 있다면?….100만번 반복해야 될 수도 있습니다 😟 )
• (이말은 만약에 찾고자 하는 값이 인덱스 0번에 위치하면 한번의 반복으로 찾지만, 만약에

 

이진검색(Binary Search)

이진검색은 다른말로는 이분검색. 이라고도 합니다! (계속 반으로 나누어서 값에 도달하기 때문에)

선형검색은 최악의 경우 10억개의 데이터가 있으면 0번째 부터 10억번까지

반복해서 찾아야 했습니다…

하지만 이진검색은 중간값부터 탐색을 시작해서 그 범위를 계속 반절씩 나눠가며 최종값에 도달

합니다 . ex( 10억의 데이터 ⇒ 5억의 데이터 ⇒ 2.5억 데이터…….

그렇기에 처리속도가 매우 빠른데, 실감이 잘 안되죠 이렇게 말하니 엣흠.

이진검색 선형검색

70억명	70억명
최대 33번 반복	최대 70억번 반복

숫자만 봐도 엄청 줄었죠…? 일단 이렇게 납득이 가면 :

“올ㅋ 어떻게 쓰는지 함 봐야겠다”

하지만..!

무언가 좋아진 만큼 다른것은 덜 좋아졌겠죠?????

그것은 바로 이진검색 은 정렬된 데이터 집합에서만 사용이 가능하다는것 입니다.

엥 이게 무슨말이여?….

정렬된 데이터란?

예를들어 데이터의 값이 정수라고 가정하면 숫자 1부터 10억 까지 있는 데이터의 집합이 있다고

가정합니다. 만약에 여기 있는 숫자들이 순서가 오름차순이 아니라 무작위로 섞여 있다면?….

반으로 나눠서 범위안에 존재하는지 탐색이 불가능 하겠죠…..

결론: 정렬된 데이터란 특정한 공식, 순서를 기준으로 말 그대로 “정렬” 해놓은것 입니다.

그렇다면 이진검색은 어떻게 쓸까?

---

코드:

int BinarySearch(int arr[], int size, int target)
{
    int first = 0;     //정수형의 정렬된 데이터라는 기준으로 0부터 시작.
    int last = size - 1;
    int mid;
 
    while(first <= last)
    {
        mid = (first + last) / 2;
        if(target == arr[mid])
            return mid;
        else if(target < arr[mid])
            last = mid-1;
        else 
            first = mid + 1;
    }
    
    return -1;
}

위에 코드 예시를 보면서 같이 정리해보겠습니다!

일단 세가지 변수를 선언을 해놨는데,

first 에 해당되는 변수는 탐색 범위중 최저값 입니다.

last 에 해당되는 변수는 탐색 범위중 최고값 입니다.

mid 에 해당되는 변수는 최고값+최저값을 나누기 2 한것입니다.

자 변수에 들어간 데이터값들의 역할을 알았으니 이제 예를 들어보겠습니다!

저희가 찾아야 하는 값은 배열안에 있고 그 배열은 총 20개의 데이터를 가지고 있습니다.

그렇다면 저희는 일단 범위를 반절로 줄여야 겠지요?? (이진검색 이니까요 !)

---

밑에 코드를 보면 while문을 이용하여 first ≤ last 가 값이 true 일때 까지만 반복을 합니다.

즉 최저값이 최대값보다 크면 반복문이 멈춰지는거죠?? 혹은 최대값이 최저값보다 작아거나요!

왜? 이렇게 범위를 설정했냐??

계속해서 반복하다 보면 어느 순간 둘의 값이 서로를 초과하거나 적어지는 현상이 일어나면 탐색을

끝까지 했다는 소리이기 때문입니다 🙂

 

 

    while(first <= last)
    {
        mid = (first + last) / 2;
        if(target == arr[mid])
            return mid;
        else if(target < arr[mid])
            last = mid-1;
        else 
            first = mid + 1;
    }
    
    return -1;

mid 변수는 첫 코드표에서 보면 생성만하고 초기화는 안했습니다. 그이유는 바로~~

반복문안에서 초기화가 계속 진행되어야하고, 그값이 계속해서 mid에 전달이 되고 적용이 되어야 해서 그렇습니다.

자자 여기까지 이해가 됬다면 위에 있는 식이 이제 엄청 간단하고 보기 쉬워질겁니다 !!!

mid값은 최고값 + 최저값을 나누기 2 한것

“만약에” 찾고자하는 값인 target 이랑 arr[mid] 값과 일치 한다면? 이 말은 곧

탐색범위를 반으로 줄였는데 거기에 있는값이 제가 찾고있던 값이라는 뜻이죠 🙂

근데 만약에 찾고 있던 값이 아니라면요?

밑에 있는 else if문을 만나 탐색범위를 줄여줍니다!!!

 

 

 

 

• 만약 찾고자 하는 값이 배열의 중간에 있는 값보다 작다면? else if (target < arr[mid] )

     그렇게 되면 범위가 만약에 20개 데이터를 가진 배열이라면 처음에 반절로 나눈 10이 
  

  mid값이고 현재 mid 값보다 찾고자 하는 값이 적다고 했으니 최대값의 범위를 다시 반절로 줄여줍니다! 그러고 나서 실행을 다시 돌게 되면 10/2 를 해서 5가 되겠죠??

 

 

• 이걸 무한 반복 하다가 값을 찾거나 없으면 return -1을 만나서 빠져나가는겁니다~
• ⇒ last = mid - 1; 최고값을 반절값에 -1을 해서 초기화 시켜줍니다.
• 만약 찾고자 하는 값이 배열의 중간에 있는 값보다 크다면? else if (target > arr[mid] )반복 과정은 역시 위와 동일하게 계속해서 반절로 초기화 시켜서 탐색합니다.
• ⇒ first = mid + 1; 최저값을 반절값에 +1을 해서 초기화 시켜줍니다.

<aside> 💡 자 이렇게 크고 작고를 판가름 하여 범위를 계속 반절로 줄여나가 데이터에 도달합니다!

</aside>

---