[알고리즘] 이진 탐색

오늘은 이진 탐색 알고리즘에 대해 공부해보았다.

 

이진 탐색 알고리즘이란?

간단하게 말해서 리스트의 크기가 커질수록 순차탐색보다 빠르게 검색할 수 있는 알고리즘이다.

다만 2진 탐색을 하기위해서는 값에 대해 정렬이 필수이다.

 

그럼 간단하게 설명해보겠다. 이진 탐색은 정렬한 배열에서 특정한 값을 찾고자 할 때 배열의 중간에 있는 임의의 값을 선택하여 우리가 특정한 값과 비교하고 특정한 값이 임의의 값보다 작으면 그것을 기준으로 좌측의 데이터들을 대상으로, 그 반대로는 우측을 대상으로 탐색을 반복하며 특정한 값을 찾는 것이다.

말로 풀어내면 어렵다. 실제 배열이 있다고 가정하고 구해보자.

 

{1, 5, 27, 46, 66, 82, 98, 100}           이러한 배열에서 특정한 값 46을 찾아보겠다.

 

1. 우선 가장 먼저 해야할 일은 중간 값을 특정하는 것이다. 우리가 자주하는 추측성 게임 UP DOWN과 좀 비슷할지도?

중간 값 == 66 이므로 우리가 찾을 값은 46<66 , 66보다 좌측배열에 존재한다.

 

{1, 5, 27, 46}   // 66을 기준으로 좌측만 짤라온 것이다.

 

2. 그 다음도 똑같게 진행한다. 홀수가 아니니 정확하게 중간 값을 구할 수는 없지만 그냥 중간 근처로 충분하다.

임의의 값을 27로 잡고 하게 된다면 27<46 이므로 27기준으로 오른쪽만 잘라오면 된다.

 

{46}

 

3. 우리가 원하는 특정한 값만 남게 되므로 이진탐색이 종료된다.

 

4. (If) 만약 우리가 찾아야 할 특정한 값이 배열에 존재하지 않으면 어떻게 될까?^[각주:1]

 

이번엔 코드를 직접 봐보도록하자

여기서 주의해야 할 것은 값은 보는게 아닌 값을 담고있는 Index를 봐야한다.( 물론 값도 봐야함)

int[] arr = new int[11];

for(int i =0; i<arr.length; i++) {
    arr[i]=i*5; //{0, 5, 10, 15, 20, 25, 30, 35, 40, 45, 50}
}

int lowIndex = 0;
int highIndex = arr.length-1; //배열의 크기가 11이니까 제일 높은 인덱스는 10
int midIndex = 0;
int target = 15; //우리가 원하는 값

while(lowIndex <= highIndex) {
    midIndex = (lowIndex + highIndex) / 2; //중간 배열 index 측정

    if(arr[midIndex] == target) //만약 target의 값과 일치하면 탈출.
        break;
    else if(arr[midIndex] > target) // target보다 크면 highIndex를 하나 감소
        highIndex = midIndex -1;
    else
        lowIndex = midIndex +1; // target보다 작으면 lowIndex를 하나 증가
}
System.out.println(midIndex); //3번째
System.out.println(arr[midIndex]); //arr[3]의 값이 15 == target이다 !

 

그리 어렵지 않아서 천천히 읽어보면 반드시 이해할 수 있다.

보통은 매소드로 만들어서 사용하니 인자값에 배열과 target값을 넘겨주고 midIndex를 반환시키면 메소드 완성이다.

 

재귀함수를 이용하는 것도 있는데 나중에 시간을 내서 그것도 추가해보도록 하겠다 !!

 

 

 

 

 

 

 

알고리즘이라해서 겁먹을 필요는 없다고 생각한다. 알고리즘은 그냥 주어진 문제를 빠르게 효율적으로 해결하는 방법이며 이것은 우리가 살고있는 현실세계에도 똑같이 있으니까, 라고 생각하면서 받아들여보자^[각주:2]

1. 과정은 똑같게 반복되지만 배열이 점점 줄어들고 결국 마지막에는 배열에 아무것도 남게 되지 않는다. 또 다른 종료조건인 것이다. [본문으로]
2. 라고 나에게 [본문으로]