(Easy - Binary Search) Leetcode - 704 : Binary Search

이진 검색을 사용해 원사는 값의 index를 찾는 문제입니다.

 

이진 검색은 정렬되어 있는 배열에서 중간의 값을 선택해, 그 값과 찾고자 하는 값을 비교해 찾는 방식입니다.

만약 중앙값이 찾는 값보다 크면 그 값은 새로운 최대값이 되고, 작으면 그 값은 새로운 최솟값이 됩니다.

그 후 다시 최소값과 최대값의 index를 사용해 그 중앙값을 찾아 비교를 목표값을 찾을 때까지 반복해줍니다.

 

int search(std::vector<int>& nums, int target) {
        int l = 0, r = nums.size() - 1;

        while (l <= r) {
            int mid = l + static_cast<int>((r - l) * 0.5f); // 중간 값

            if (nums[mid] > target) // 중간 값이 더 크면
                r = mid - 1;
            else if (nums[mid] < target) // 중간 값이 더 작으면
                l = mid + 1;
            else // 찾았으면 index를 return
                return mid;
        }

        return -1; // 배열에 없으면
    }