[LeetCode] 704. Binary Search(Java)

Binary Search - LeetCode

📚 문제

Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.

 

You must write an algorithm with O(log n) runtime complexity.

 

Example 1:

Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 exists in nums and its index is 4

Example 2:

Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1
Explanation: 2 does not exist in nums so return -1

 

📝 문제 해결

이진탐색 문제로 이진탐색 알고리즘이란, 탐색 범위를 줄여 원하는 데이터를 찾는 시간 복잡도를 O(logN)으로 줄여주는 알고리즘으로

• 배열 내부의 데이터가 정렬되어 있어야만 사용 가능
• 시간 복잡도 : O(logN) 한 번 확인할 때마다 확인하는 원소의 개수가 절반씩 줄어든다

 

이진 탐색 동작방식

• 위치를 나타내는 변수 3개 (시작점, 끝점, 중간점)을 사용하여 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교

1) 배열 / 시작점 / 끝점 / 찾고자하는 데이터 - 4개가 주어진다.
2) 시작점과 끝점의 중간점을 구한다.
3) 중간점이 가리키는 값이 찾고자하는 데이터면 끝
3-1) 중간점이 찾고자하는 데이터보다 크면 끝점을 중간점-1로,
3-2) 중간점이 찾고자하는 데이터보다 작다면 시작점을 중간점+1로 설정

 

이진 탐색 구현방법

• 재귀 함수

package search;

import java.util.Scanner;

public class search07 {
    public static int binarySearch(int[] arr, int target, int start, int end){
        if(start > end) return -1;
        int mid = (start + end)/2;
        if(arr[mid] == target) return mid;
        // 중간점의 값보다 작은 경우 왼쪽으로 끝점 이동
        else if(arr[mid] > target) return binarySearch(arr, target, start, mid-1);
        // 중간점의 값보다 큰 경우 오른쪽으로 시작점 이동
        else return binarySearch(arr, target, mid+1, end);
    }

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int target = sc.nextInt();

        int[] arr = new int[n];
        for(int i=0; i<n; i++){
            arr[i] = sc.nextInt();
        }

        int result = binarySearch(arr, target, 0, n-1);
        if(result == -1) System.out.println("원소가 존재하지 않습니다.");
        else System.out.println(result+1);
    }
}

 

• 반복문

public static int binarySearch(int[] arr, int target, int start, int end) {
	while (start <= end) {
		int mid = (start + end) / 2;
        if (arr[mid] == target) return mid;
        else if (arr[mid] > target) end = mid - 1;
        else start = mid + 1;
    }
    return -1;
}

이진 탐색은 코딩 테스트에서 단골로 나오는 문제이니 가급적 외우길 권함

더불어 범위가 큰 상황에서의 탐색을 가정하는 문제에 많이 나온다.

처리해야 할 데이터의 개수나 값이 1000만 단위 이상으로 넘어가면,
이진 탐색과 같이 O(logN)의 속도를 내야 하는 알고리즘을 떠올려보자!

 

💻 코드

class Solution {
    public int search(int[] nums, int target) {
        int start = 0;
        int end = nums.length - 1;
        int mid = 0;

        while(start <= end){
            mid = (start + end) / 2;
            if(target == nums[mid]) return mid;
            else if(nums[mid] < target) start = mid + 1;
            else if(target < nums[mid]) end = mid - 1;
        }

        return -1;
    }
}