[리트코드/자바] 704. Binary Search

문제

정렬된 배열 nums와 찾고자 하는 정수 target이 주어질 때, target에 해당하는 nums의 index를 찾으세요. 만약 target이 배열 내에 존재하지 않는다면 -1을 리턴하세요.

 

테스트케이스

• nums = {-1, 0, 3, 5, 9, 12}
  target = 9
  output: 1

 

• nums = {-1, 0, 3, 5, 9, 12}
  target = 2
  output: -1

 

해설 및 풀이

로직

1. 배열의 양 끝에 Left, right를 지정하고, 그 중앙에 위치한 값을 mid로 설정한다.
2. target이 mid보다 크다면, left~mid구간을 탐색하며,
   target이 mid보다 작다면, mid~right구간을 탐색한다.
3. 탐색하는 범위(길이)가 2가 될때까지 이를 반복한다.
4. left, right값을 비교해서 target의 위치를 확인한다.

 

💡 중앙값과 오버플로우
중앙값을 구하는 방법은 (left+right)/2 를 통해서 할 수 있다. 하지만, 만약 left+right의 연산 결과값이 int 타입 표현범위를 벗어나는 경우엔 오버플로우가 발생할 수 있다. 이를 간단하게 피하는 방법은 중앙값의 의의를 통해 알 수 있다. 

중앙 = 두 점 사이에서 각 점으로부터 동일한 거리에 위치한 지점

따라서, 각 점으로부터 동일한 거리(m)를 구하고, 시작점을 기준으로 m만큼 떨어진 곳의 위치를 구하면 된다. 이에 대한 수식은 다음과 같다. 

mid = ((max-min) / 2) + min

 

자바 구현코드

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

 

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

Binary Search - LeetCode