[Array] 이진탐색

이진 탐색 문제는
배열이 정렬되어있을때 우리가 원하는 엘레멘트를 찾아달라는 문제입니다. 만약 선형탐색을 진했을때는 하나하나 엘레멘트를 탐색해야하기 때문에 O(N)의 시간 복잡도가 발생하죠. 그런데 이진 탐색을 사용한다면 O(logN)의 시간 복잡도로 탐색할 수 있어요.

직접 구현하기 위해서는 레프트,라이트,그리고 피봇이 필요합니다. 우선 레프트는 배열의 첫인덱스를 가리키고, 라이트는 배열의 마지막 인덱스를 가리켜요. 그리고 피봇은 항상 (레프트 + 라이트)/2의 인덱스를 가리키게되요. 만약 2.5처럼 나누어 떨어지지 않는 수는 int형이기 때문에 .5를 버리고 2번 인덱스를 기르키게 되요.

피봇을 찾았다면 우리가 찾고있는 수와 피봇을 비교해보고 같으면 리턴하고 피봇의 엘레멘트보다 작은수라면 피봇 오른쪽 인덱스를 볼 필요 없기 때문에 라이트를 피봇의 왼쪽 인덱스(피봇 - 1)까지 끌어와요. 이제 다시 피봇을 (레프트 + 라이트)/2의 인덱스를 가리키게 하고, 또 찾고 있는 수와 비교해요.
이런식으로 찾고싶은 수를 찾을때까지 탐색 범위를 절반으로 줄여가며 탐색을 진행합니다.

그리고 만약 배열안에 찾고 싶은 수가 없다면, 레프트 인덱스와 라이트 인덱스가 같은 인덱스를 가리키게 되요. 이때 피봇도 업데이트가 되면서 (레프트 + 라이트)/2가 레프트 라이트와 같이 한 인덱스에서 다같이 만나게 되고, 마지막으로 라이트가 왼쪽으로 움직이면서 레프트와 라이트의 위치가 반전됩니다. (레프트 + 라이트)/2가 -1이되고 피봇이 -1을 가리킨다면 찾고 싶은 수가 없다고 판단하고 반복문을 종료해요.

구현

int serch(int[] nums, int target)	//출제자로 부터 배열과, 찾을 숫자를 받게됩니다.
{
    int left = 0; 
    int right = nums.Length -1;

    while (left <= right)
    {
        int pivot = (left + right) / 2;
        if (nums[pivot] == target)
        {
            return pivot;
        }
        else if (nums[pivot] < target)
        {
            left = pivot + 1;
        }
        else //target < nums[pivot] || left,right,pivot이 한 인덱스에서 만날때(숫자를 못찾음)
        {
            right = pivot - 1;
        }
    }

    return -1;
}