Sequential search, Binary search

선형적인 배열에서 특정 값을 찾는 방법으로 Sequential search 와 Binary search 방법이 있습니다.

Sequential search 은 말 그대로 배열의 앞에서부터 끝까지 차례대로 찾아가는 방법이고

Binary search 는 오름차순으로 정렬된 배열에서 divide and conquer algorithm 을 사용하여 찾을 대상을 절반씩 줄여가는 방법으로 시간 복잡도를 줄이는 방법입니다.

Binary search 는 최악의 경우에서도   을 보장하기 때문에 크기가 큰 배열에서는 일반적으로 Sequential search 보다 빠르게 값을 찾을 수 있습니다.

https://en.wikipedia.org/wiki/Linear_search

https://en.wikipedia.org/wiki/Binary_search_algorithm

int sequentialSearch(int* numbers, int arrSize, int target)
{
    for (int i = 0; i < arrSize; i++)
    {
        if (target == numbers[i])
            return i;
        //else if (x < numbers[i])    //if array is sorted, it can use.
        //    return -1;
    }
    return -1;
}
int binarySearch(int* numbers, int arrSize, int target)
{
    int low = 0;
    int high = arrSize - 1;
 
    while (low <= high)
    {
        int mid = (low + high) / 2;
        if (numbers[mid] > target)
            high = mid - 1;
        else if (target > numbers[mid])
            low = mid + 1;
        else
            return mid;
    }
 
    return -1;
}