# ์ด๋ถ„ ํƒ์ƒ‰(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[arr.length-1]; // ๋
	
	while(start <= end) {
		
		int sum = 0;
		int mid = (start+end)/2; // ์‹œ์ž‘๊ณผ ๋์˜ ์ค‘๊ฐ„๊ฐ’
		
		for (int i = 0; i < arr.length; i++) {
			if(arr[i] > mid)
				sum+=mid;
			else
				sum+=arr[i];
		}
		
		if(sum > M)
			end = mid - 1;
		else
			start = mid + 1;
		
	}
    
	return end;
}




์ตœ์ข… ์ˆ˜์ • : 11/15/2021, 1:31:19 PM