글 읽기 - 이진검색 이용했는데 어떤 방식은 되고 어떤 방식은 안되네요

aldrlsb11 5년 전 0

code에서 이진 검색을 활용했습니다

그런데 이진 검색을 두 가지 방식으로 짜봤는데, biSearch1에선 결과가 맞고, biSearch2에선 결과가 틀리네요

Q.1 근사치를 찾는 경우에는 biSearch1이 2보다 더 촘촘하게 검색을 하는 것인가요?

Q.2 아님 우연히 biSearch1이 맞은 것 뿐인가요? 왠지 다른 테케에선 작동 안할 수도 있다는 생각이 드네요.

package practice;

import java.util.*;

public class Main7 {

    public static int biSearch1(int find, int arr[]) {
		int left = 0;
		int right = arr.length;
		int mid = 0;
		while (right - left >= 1) {
			mid = (left + right) / 2;
			if (arr[mid] == find)
				return mid;
			if (arr[mid] < find) {
				left = mid + 1;
			} else {
				right = mid;
			}
		}
		return mid;
	}

	public static int biSearch2(int find, int arr[]) {
		int mid = 0;
		int left = 0;
		int right = arr.length - 1;
		while (left <= right) {
			mid = (left + right) / 2;
			if (arr[mid] == find) {
				return mid;
			}
			if (arr[mid] < find) {
				left = mid + 1;
			} else {
				right = mid - 1;
			}
		}
		return mid;
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int num[] = new int[n];
		for (int i = 0; i < n; i++) {
			num[i] = sc.nextInt();
		}
		int min = Integer.MAX_VALUE;
		int a1 = -1;
		int a2 = -1;
		for (int i = 0; i < n; i++) {
			int index = biSearch1(-num[i], num);
            if (i == index) {
                continue;
            }
			int val = (int) Math.abs(num[i] + num[index]);
			if (min > val) {
				min = val;
				if (num[i] < num[index]) {
				a1 = i;
				a2 = index;
			    } else {
				a1 = index;
				a2 = i;
				}
			}
		}
		System.out.println(num[a1] + " " + num[a2]);
	}
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

이진검색 이용했는데 어떤 방식은 되고 어떤 방식은 안되네요

aldrlsb11 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말