[C] Binary Search 구현

주어진 배열에 target값이 있다면 인덱스 리턴, 없다면 -1리턴

Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1

https://leetcode.com/problems/binary-search/submissions/

사내테스트에서 문제 다 풀었는데, 시간복잡도 개선(N -> logN)을 위해 binary search만 구현하면 되는 상황이었음. 근데 결국 구현못해서 TLE나옴. 억울ㅜㅜ
left, right, mid 인덱싱을 제대로 못함... 그냥 외우자.

참고로 주의할 사항. 못찾았을때 -1를 리턴하기 위해서는 while의 조건을 (left <= right)로 해야함 (left < right)는 안됨.

int bin_search(int *nums, int numsSize, int tgt)
{
    int left = 0;
    int right = numsSize - 1;
    int mid = 0;
    
    while (left <= right) {
        mid = (left + right) >> 1;
        if (tgt == nums[mid])
            return mid;
        else if (tgt < nums[mid])
            right = mid - 1;
        else if (tgt > nums[mid])
            left = mid + 1;
    }
    return -1;
}

int search(int* nums, int numsSize, int target){
    return bin_search(nums, numsSize, target);
}