[LeetCode] 704 Binary Search

정렬된 배열이 주어지고, 거기서 target을 가지고 있는 인덱스를 리턴하라. 없다면 -1을 리턴

시간 복잡도는 O(log n)이여야 한다. 

class Solution {
    public int search(int[] nums, int target) {
        
    }
}

 

정렬된 배열에서 원하는 target을 찾는 방법으로 binary search가 있는데 

이를 구현하는 문제이다. 

 

{
    int left = 0, right = nums.length - 1;

    while (left <= right) {
        int mid = left + (left + right) / 2;

        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] < target) {
            left = mid + 1;
        }

    }
    return -1;
}

문제를 풀다 햇갈렸던 부분으로는 while을 진행하는 조건에 left, right 값 비교에서 

값이 같은 경우를 포함해야하는지 여부였다. 

 

left, right가 같은 경우에도 search를 진행해야 한다. 

-> 둘의 값이 같은 경우를 target인지 검증하지는 않았기 때문