이진탐색

이진탐색을 하기 위해서는 데이터가 정렬이 먼저 되어 있어야 한다.

배열 { 1, 2, 4, 5, 6, 10,13,15 } 에서 4 ( = target값) 를 찾는다고 가정하자.

이진탐색의 기본 방법은 left의 Index와 해당 범위 내의 right Index를 2로 나뉘어 mid값을 찾아가는 가정이다.

처음의 mid = (0+7)/2

arr[mid] = arr[3] = 5 즉, 우리가 찾고자 하는 값보다는 크다.

그럴 때는 right의 값을 현재 mid - 1을 해준다.

만약 target 값이 컸다면 left = mid+1을 해준다.

두번쨰 mid = (0+2)/2;

(right = mid-1)을 해줬음.

arr[mid] = arr[1] = 2, 즉 우리가 찾고자 하는 값보다는 작다

세번째 mid = (1+2)/2;

(left = mid+1)을 해줬음

arr[mid ] = arr[1] 

4번쨰 mid = (2+2)/2;

(left = mid+1)을 해줬음

arr[mid] = arr[2] = 4, 즉 우리가 찾고자 하는 값을 찾았다.

시간복잡도는 O(logn)

 

void binary_search(int arr[], int len, int target){

    

    int left = 0;

    int right = len-1;

    

    while(left<=right) {

        

        int mid = (left+right) / 2;

        

        if(arr[mid] == target){

            System.out.println(“FIND”);

            return mid;

        }

        else if(arr[mid] > target){

            right = mid-1;

    

        }

        else{

            left = mid+1;

        }

    }

}