[Easy] 704. Binary Search

Leetcode 704번 문제는 integer array와 target value가 주어지면 binary search (이진 탐색)을 사용해 target value를 찾아내는 문제이다. 이진 탐색을 사용해야 하기 때문에 너무나 당연하지만 풀이 과정에서 time complexity (시간 복잡도)는 O(log n) 이 돼야 한다.

 

#풀이

class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while(left <= right){
            int mid = (left + right) / 2 ;
            if(nums[mid] == target){
                return mid;
            }
            
            if(target > nums[mid]){
                left = mid + 1;
            }
            else if(target < nums[mid]){
                right = mid - 1;
            }
        }
        return -1;
    }
}

처음에는 맨 왼쪽 index와 맨 오른쪽 index를 각각 left와 right 변수로 지정해준다. 그 다음, while loop 안에서 가운데 index 를 mid 변수에 저장해준다. 그리고 mid index에 있는 값이 target value와 같으면 mid index를 return 해준다, 그렇지 않으면 mid index에있는 값이 target value값보다 작거나 큰지 확인하고 크면 배열 왼쪽 절반에 있는 값들은 필요가 없어지기 때문에 (binary search는 정렬된 자료구조에서 밖이 쓸 수 없기 때문) left값을 mid + 1, 즉 오른쪽으로 당겨준다. 만약 반대로 target값이 더 작으면, 반대로 right값을 오른쪽으로 당겨 주면 된다. 이 과정을 while loop으로 반복해주고, 만약 target 값을 찾지 못하면 -1을 return 해주면 된다.