# ์ด๋ถ„ ํƒ์ƒ‰(Binary Search)



ํƒ์ƒ‰ ๋ฒ”์œ„๋ฅผ ๋‘ ๋ถ€๋ถ„์œผ๋กœ ๋ถ„ํ• ํ•˜๋ฉด์„œ ์ฐพ๋Š” ๋ฐฉ์‹

์ฒ˜์Œ๋ถ€ํ„ฐ ๋๊นŒ์ง€ ๋Œ๋ฉด์„œ ํƒ์ƒ‰ํ•˜๋Š” ๊ฒƒ๋ณด๋‹ค ํ›จ์”ฌ ๋น ๋ฅธ ์žฅ์ ์„ ์ง€๋‹˜

* ์‹œ๊ฐ„๋ณต์žก๋„
์ „์ฒด ํƒ์ƒ‰ : O(N)
์ด๋ถ„ ํƒ์ƒ‰ : O(logN)

# ์ง„ํ–‰ ์ˆœ์„œ

  • ์šฐ์„  ์ •๋ ฌ์„ ํ•ด์•ผ ํ•จ
  • left์™€ right๋กœ mid ๊ฐ’ ์„ค์ •
  • mid์™€ ๋‚ด๊ฐ€ ๊ตฌํ•˜๊ณ ์ž ํ•˜๋Š” ๊ฐ’๊ณผ ๋น„๊ต
  • ๊ตฌํ•  ๊ฐ’์ด mid๋ณด๋‹ค ๋†’์œผ๋ฉด : left = mid+1 ๊ตฌํ•  ๊ฐ’์ด mid๋ณด๋‹ค ๋‚ฎ์œผ๋ฉด : right = mid - 1
  • left > right๊ฐ€ ๋  ๋•Œ๊นŒ์ง€ ๊ณ„์† ๋ฐ˜๋ณตํ•˜๊ธฐ

# ์†Œ์Šค ์ฝ”๋“œ

public static int solution(int[] arr, int M) { // arr ๋ฐฐ์—ด์—์„œ M์„ ์ฐพ์ž
	
    Arrays.sort(arr); // ์ •๋ ฌ
	
    int start = 0;
    int end = arr.length - 1;
    int mid = 0;

    while (start <= end) {
        mid = (start + end) / 2;
        if (M == arr[mid]) {
            return mid;
        }else if (arr[mid] < M) {
            start = mid + 1;
        }else if (M < arr[mid]) {
            end = mid - 1;
        }
    }
    throw new NoSuchElementException("ํƒ€๊ฒŸ ์กด์žฌํ•˜์ง€ ์•Š์Œ");
}




์ตœ์ข… ์ˆ˜์ • : 10/3/2022, 1:23:47 PM