[GeeksforGeeks: 알고리즘 기초 2편] 이진 탐색(Binary Search)

장황하고 쓸데없는 내용이 많은 1편이 끝나고...

 

[GeeksforGeeks: 알고리즘 기초 1편] 선형탐색(Linear Search)

못 본 제군들은 여기 가서 복습하시오. 글을 다시 쓰는 필자도 잠깐 읽고 옴 개념 복습을 위해서!!! (항상 자신의 실력에 대해 겸손 할 것)

이번 이진탐색은 많은 비전공자들이 알고리즘을 진입할 때 가장 먼저 포기하는 레벨이자 기초임.

쉽지만 의외로 어렵게 생각하시는 분들이 많아서 포스팅이 상당히 길어졌음! 가능한한 많은 사람들이 이해하길 바래서 길게 씀 본인에게 쉬운 개념이라면 중간에 뛰어 넘기며 읽는 것을 권장함.

 

아 그리고... (급 존대) 제가 이해하는거랑 누군가에게 가르치는 것은 확실히 다른 영역 같습니다. 중견급 이상 개발자분들은 귀엽네 하고 풋 하고 웃고 넘어가 주시면 좋겠고, 초심자들에겐 그동안 이해하지 못한 알고리즘을 이해하는 기회가 되었으면 좋겠습니다.

 

미드레벨 이상급들에겐 예능(Entertainment)이고, 초심자들에겐 학습형 다큐(Educational Documentary)이길 바라는 마음으로 포스팅을 시작합니다. 저처럼 Dum 한 사람도 옳거니 하면서 이해하고 깨달음을 얻어가는 구간인 만큼 많은 분들에게 유익하길!

 

[수도 레벨(Psuedo Level)]

 

a) 2진? 이진 이진수가 뭘까? (초등학생주의)

이진 탐색(Binary Search) 제군들 모두 뭔진 알고 있을 거라 짐작이 되오.

그래도 부연 설명을 하자면.... 이진(Binary)은 1011(2진수) = 11 (10진수) = B(16진수)를 의미하고 0,1은

경우의 수로 가면 true & false 또는 양자택일이라는 개념이라오.

 

즉 두 가지 경우의 수를 임의로 만들고, 고르는 알고리즘이라고 생각하면 편하리라 잠식이 되오. 

사진을 보고 이해가 된다면 [코드 레벨 풀이]로 넘어가시오.

부디 남아있는 제군들을 무시하진 마시오. 다들 걸어봐야 뛸 수 있고 뛰어봐야 자전거든 차든 운전할 수 있고 그런 시기가 있으며 당신들 회사 후배들이 그런 입장일 수도 있다는 걸 항상 염두하시오.

 

b) 정렬(Sort)? 오름차순(Ascending)? 내림차순(Descending)? 마찬가지로 초등학생 주의

이 문제는 특정 배열에 있는 수 arr  = [2,5,8,16,23,38,56,72,91] Damn! 보고 느끼는 거 없소?

필자가, 초등학생이 할법한 보고 따라 치기 했다는 거 외에도,

숫자들이 오름차순(Ascending)으로 아주 예쁘게(Nice) 정렬(Sort) 돼있지 않소. 이 정렬에 대한 방법도 여러 가지이며 성능적 측면을 따진다면 다양한 논제가 나올 수 있지만... 이번 포스팅에서는 숫자가 앞뒤로 오르락(Ascend) 내리락(Descend) 정렬(Sort)되는 걸 이해만 하고 넘어가세!

이게 어렵다면... 초등학교 1~6학년 수학 교과서를 한번 잘 찾아보시거나 정렬의 정의를 한번 다시 읽어보시길... 흠흠

 

c) 이진수랑, 정렬은 도대체 왜 같이 나온 건데? 이진 탐색 (본격 경우의 수! 비교하기)

자 예쁘게 정렬이 돼있음. What the fuck 그래서 이진(Binary) 탐색(Search)랑 오름차순(Ascending) 또는 내림차순(Descending) 정렬(Sort)이랑 도대체 무슨 관계인데? (직관적으로, 이해가 되면 아래 단락 무시하고 넘어가시고)

 

이진수(경우의 수로 양자택일), 숫자 찾기? 아주 잘만 생각하면, 숫자 또는 데이터(string int bool... 등등 모든 값들 컴퓨터는 어차피 숫자로 인식함... 이건 코볼 펄 파스칼 등 고전 언어를 공부할 때 나오는 개념이며 컴퓨터 개론을 보면 알 거예요... 그 정도로 딥하게 가진 않겠음. 굳이 열거한 이유는 궁금하면 찾아보란 소리))라는 변수(Attribute)가 가진 속성(property)을

 

크고 작음을 잘 생각 해보삼, 우리가 숫자를 찾을 때는 크고 작음으로 찾음. 숫자에 크고 작음 외에 다른 의미가 있음?

(철학적으로 말고 쉽고 간단하게 직관적으로 제발(please)!)

 

그래서 저희는 이 이진 탐색을 하기 위해서는 다음과 같은 변수가 필요함.

a) x(함수의 미지수이자 우리가 찾고자 하는 입력 값)

b) array(찾고자 하는 값이 있는 배열 리스트 해시 json 어떤 타입이건 상관없이 그냥 데이터의 집합체요 제발(please)!),

c) 오름차순 기준 제일 큰 가장 끝 값 H(high) // 내림차순이면 반대ㅇㅋ?

d) 오름차순 기준 제일 작은 가장 시작 값 L(Low) // 내림차순이면 반대ㅇㅋ?

e) 그리고 크고 작음을 기준하는 중간 값 M(Mildde) // 내림차순 오름차순 상관 없ㅇㅋ?

 

arr에서 L ~ H 전체 구간

arr에서 L ~ M 낮은 값 구간

arr에서 M ~ H 높은 값 구간

x 입력 값 ㅇㅋ?

 

자 그러면... 경우의 수는 다음과 같음.

a) M = x? Lucky 하게 바로 m리턴하는 조건문을 넣자.

 

b1 ) x > M? 오우 쉣 그러면 L ~ M 구간을 버리고 M보다 바로 더 큰 값이 이 L이 됨?

L ~ H 가 새로 정의되고 새로운 M(2)을 정의됨.

M(2) = x?  Lucky 하게 바로 m리턴하는 조건문을 넣자.

그게 아니면 b1을 또 계속 반복하는(recursive) 조건을 만들면 됨.

 

b2) x < M? M ~ H를 버리고 기존의 M보다 바로 더 작은 값이 H가 됨.

b1과 마찬가지로(정반대의 배열 값이겠지만)

L ~ H 가 새로 정의되고 새로운 M(2)을 정의됨.

M(2) = x?  Lucky 하게 바로 m리턴하는 조건문을 넣자.

그게 아니면 b1을 또 계속 반복하는(recursive) 조건을 만들면 됨.

 

어렵나요?

23을 찾는 문제로 예를 들어 아까 올린 뭔 말인지 하나도 모르겠던 그림을 다시 설명드림.

int arr  = [2,5,8,16,23,38,56,72,91];라는 간단하고 예쁘게 잘 오름차순 정렬된(fucking simple & Nice Ascending Sorted) 배열로 방금 드린 풀이로 친절하게 한 줄 한줄 설명을 드리자면.

 

a) 2번 줄 풀이!

(1번은 배열 선언이라 풀이를 얘기하면 철학적인 소리를 할거 같음, 하아 제발(please))

정렬된 배열에서 주소를 정의하면 L의 주소는 0, M의 주소는 4, H의 주소는 9 임. (왜 인지는 골백번도 넘게 설명했듯이 오름차순 정렬이 돼있기 때문! 모르면 혼나야 됨 이제!)

해당 주소의 값이 다음과 같음.

 

L(1st) = arr[0] = 2

H(1st) = arr[9] = 91

M(1st) = arr[4] = 16

 

x : 23 vs M(1st) : 16 누가 더큼? x : 23

 

b) 3번 줄 풀이입니다.

그러면 initial M = arr[4] = 16 이하의 모든 수를 쓰레기통에 처박음.

L(2nd) = arr[5] = 23 // 정답이 나왔을 거라고 생각할 수 도 있지만 이 예제에는 M값과 x만 비교질 하므로 컴퓨터는 이걸 정답이라고 인지하지 못함. 이 시점에 정답을 리턴하게 하려면 어떻게 짜면 되냐면, 사실 심플함 힌트는 루프 문 안에서 비교질만 몇 번 더 하면 됨.

굳이 안 그러는 건... 1 procedure당 biz를 더 심플화시키기 위함 (사람은 한 번에 이것저것 다하는 게 유능해 보이겠지만 컴퓨터는 그런 걸 지양해야 한다고 어디서 얼핏 듣고 배웠음, 비전공자 피셜이라 김풍 요리 짤 지식처럼 생각하시면 될 듯)

 

H(2nd) = arr[9] = 9

M(2nd) = arr[7] = 56

 

M(2nd) : 56 vs x: 23 누가 더큼? M(2nd) : 56

 

c) Okay 이제 마지막 줄... LMH가 또 아까 제가 말한 룰대로 M(2nd) 이상의 배열이 쓰레기통에 처박히면서 갱신됨.

L(3rd) = arr[5] = 23

H(3rd) = arr[6] = 38

M(3rd) = arr[5] = 23

이 문제에서는 M의 배열 주소 값을 floor(5+6/2)를 적용함 오름차순이라 그런 듯... 근데 굳이 M값을 그렇게 복잡하게 안 해도 됨!

 

여하튼 우여곡절 끝에 우리의 23 나옴!

요약 : 이런 식으로 위로, 아래로, 정답 3단계로 찾는 예제임. 사람 머리로 생각하면 쉽지만 컴퓨터한테 시키면 이 정도의 프로세싱이 필요함.

 

---

[코드 레벨 풀이]

 

Okay now fuck off, elementary school math teacher, and show me the code... 한번 외쳐주고 코드로 ㄱㄱ 

이게 이렇게 길게 쓰일 줄 몰랐음... 나도 설명을 좀 줄여야 하나... 헉헉...

코드레 벨을 잘 읽는 양반이라면...  그냥 보고 바로 이해할 듯?

 

C++, C은 한 세트로 쓰겠음 (내장 함수만 다르지 사실상 문법 거의 똑같음) 

// C++ program to implement recursive Binary Search 
#include <bits/stdc++.h> 
using namespace std; 

// A recursive binary search function. It returns 
// location of x in given array arr[l..r] is present, 
// otherwise -1 
int binarySearch(int arr[], int l, int r, int x) 
{ 
	if (r >= l) { 
		int mid = l + (r - l) / 2; 

		// If the element is present at the middle 
		// itself 
		if (arr[mid] == x) 
			return mid; 

		// If element is smaller than mid, then 
		// it can only be present in left subarray 
		if (arr[mid] > x) 
			return binarySearch(arr, l, mid - 1, x); 

		// Else the element can only be present 
		// in right subarray 
		return binarySearch(arr, mid + 1, r, x); 
	} 

	// We reach here when element is not 
	// present in array 
	return -1; 
} 

int main(void) 
{ 
	int arr[] = { 2, 3, 4, 10, 40 }; 
	int x = 10; 
	int n = sizeof(arr) / sizeof(arr[0]); 
	int result = binarySearch(arr, 0, n - 1, x); 
	(result == -1) ? cout << "Element is not present in array"
				: cout << "Element is present at index " << result; 
	return 0; 
} 

// C program to implement recursive Binary Search 
#include <stdio.h> 

// A recursive binary search function. It returns 
// location of x in given array arr[l..r] is present, 
// otherwise -1 
int binarySearch(int arr[], int l, int r, int x) 
{ 
	if (r >= l) { 
		int mid = l + (r - l) / 2; 

		// If the element is present at the middle 
		// itself 
		if (arr[mid] == x) 
			return mid; 

		// If element is smaller than mid, then 
		// it can only be present in left subarray 
		if (arr[mid] > x) 
			return binarySearch(arr, l, mid - 1, x); 

		// Else the element can only be present 
		// in right subarray 
		return binarySearch(arr, mid + 1, r, x); 
	} 

	// We reach here when element is not 
	// present in array 
	return -1; 
} 

int main(void) 
{ 
	int arr[] = { 2, 3, 4, 10, 40 }; 
	int n = sizeof(arr) / sizeof(arr[0]); 
	int x = 10; 
	int result = binarySearch(arr, 0, n - 1, x); 
	(result == -1) ? printf("Element is not present in array") 
				: printf("Element is present at index %d", 
							result); 
	return 0; 
} 

[특이점]

a) 근데 왜 끝자리 인덱스로 빼기 1을 2번이나 갈겼을지 잘 아는 C++ 고수분 설명 좀...  하는 말이 얼핏 들림.

상관없긴 하지만 사실 저건 그냥 모범답안 짠 양반 성향 같고(배열 연산과 홀짝 연산을 나누기 위한?)  내 추측이라면... 파라미터에 배열 인덱스를 명시화하고, 나눗셈 floor 함수를 자동 처리해서 홀짝 판단을 묵시적으로 처리하려고 그러는 거 같음, 결론은 쪼개는 게 가독성이 좀 더 높아짐 (-2를 하는 건 배열 주소와 홀짝을 동시에 처리하는 거니까)

b) 그 밖에 if 리턴 함수로 루프 문을 만드는 아주 고전적인 방법...  저것도 반복문(recursive)이긴 하지만 요새는 저렇게 잘 안 쓰죠

 

마찬가지로 java C#도 비슷하니 한데 묶겠음 (내장 함수만 다르지 사실상 문법 거의 똑같음)

// Java implementation of recursive Binary Search 
class BinarySearch { 
	// Returns index of x if it is present in arr[l.. 
	// r], else return -1 
	int binarySearch(int arr[], int l, int r, int x) 
	{ 
		if (r >= l) { 
			int mid = l + (r - l) / 2; 

			// If the element is present at the 
			// middle itself 
			if (arr[mid] == x) 
				return mid; 

			// If element is smaller than mid, then 
			// it can only be present in left subarray 
			if (arr[mid] > x) 
				return binarySearch(arr, l, mid - 1, x); 

			// Else the element can only be present 
			// in right subarray 
			return binarySearch(arr, mid + 1, r, x); 
		} 

		// We reach here when element is not present 
		// in array 
		return -1; 
	} 

	// Driver method to test above 
	public static void main(String args[]) 
	{ 
		BinarySearch ob = new BinarySearch(); 
		int arr[] = { 2, 3, 4, 10, 40 }; 
		int n = arr.length; 
		int x = 10; 
		int result = ob.binarySearch(arr, 0, n - 1, x); 
		if (result == -1) 
			System.out.println("Element not present"); 
		else
			System.out.println("Element found at index " + result); 
	} 
} 
/* This code is contributed by Rajat Mishra */

// C# implementation of recursive Binary Search 
using System; 

class GFG { 
	// Returns index of x if it is present in 
	// arr[l..r], else return -1 
	static int binarySearch(int[] arr, int l, 
							int r, int x) 
	{ 
		if (r >= l) { 
			int mid = l + (r - l) / 2; 

			// If the element is present at the 
			// middle itself 
			if (arr[mid] == x) 
				return mid; 

			// If element is smaller than mid, then 
			// it can only be present in left subarray 
			if (arr[mid] > x) 
				return binarySearch(arr, l, mid - 1, x); 

			// Else the element can only be present 
			// in right subarray 
			return binarySearch(arr, mid + 1, r, x); 
		} 

		// We reach here when element is not present 
		// in array 
		return -1; 
	} 

	// Driver method to test above 
	public static void Main() 
	{ 

		int[] arr = { 2, 3, 4, 10, 40 }; 
		int n = arr.Length; 
		int x = 10; 

		int result = binarySearch(arr, 0, n - 1, x); 

		if (result == -1) 
			Console.WriteLine("Element not present"); 
		else
			Console.WriteLine("Element found at index "
							+ result); 
	} 
} 

// This code is contributed by Sam007. 

 

 

C, C++과 비슷한 형태니까 특이점은 굳이 언급 안 하겠음

 

전혀, 비슷하진 않지만 내장 함수 import없이 귀찮음이 적은 스크립트 언어끼리는 묶곘음 (php & python3)

<?php 
// PHP program to implement 
// recursive Binary Search 

// A recursive binary search 
// function. It returns location 
// of x in given array arr[l..r] 
// is present, otherwise -1 
function binarySearch($arr, $l, $r, $x) 
{ 
if ($r >= $l) 
{ 
		$mid = ceil($l + ($r - $l) / 2); 

		// If the element is present 
		// at the middle itself 
		if ($arr[$mid] == $x) 
			return floor($mid); 

		// If element is smaller than 
		// mid, then it can only be 
		// present in left subarray 
		if ($arr[$mid] > $x) 
			return binarySearch($arr, $l, 
								$mid - 1, $x); 

		// Else the element can only 
		// be present in right subarray 
		return binarySearch($arr, $mid + 1, 
							$r, $x); 
} 

// We reach here when element 
// is not present in array 
return -1; 
} 

// Driver Code 
$arr = array(2, 3, 4, 10, 40); 
$n = count($arr); 
$x = 10; 
$result = binarySearch($arr, 0, $n - 1, $x); 
if(($result == -1)) 
echo "Element is not present in array"; 
else
echo "Element is present at index ", 
							$result; 
							
// This code is contributed by anuj_67. 
?> 

# Python3 Program for recursive binary search. 

# Returns index of x in arr if present, else -1 
def binarySearch (arr, l, r, x): 

	# Check base case 
	if r >= l: 

		mid = l + (r - l) // 2

		# If element is present at the middle itself 
		if arr[mid] == x: 
			return mid 
		
		# If element is smaller than mid, then it 
		# can only be present in left subarray 
		elif arr[mid] > x: 
			return binarySearch(arr, l, mid-1, x) 

		# Else the element can only be present 
		# in right subarray 
		else: 
			return binarySearch(arr, mid + 1, r, x) 

	else: 
		# Element is not present in the array 
		return -1

# Driver Code 
arr = [ 2, 3, 4, 10, 40 ] 
x = 10

# Function call 
result = binarySearch(arr, 0, len(arr)-1, x) 

if result != -1: 
	print ("Element is present at index % d" % result) 
else: 
	print ("Element is not present in array") 

 

마찬가지로 내장함수 안 쓰고, C, C++과 비슷한 형태니까 특이점은 굳이 언급 안 하겠음

---

두 번째 포스팅을 마치며...

이 포스팅을 할 때, 거의 떠먹여 주듯이 모든 내용을 풀어서 쓸 예정입니다.

이유는 필자가 스스로를 자칭할 때 돌대가리라고 하기 때문에(저는 진심으로(Seriously) 이해력이 높지 않습니다)

놀랍게도 2.5년 차 개발자이자 공대생 출신인 필자도 진지하게 공부에 임하는 마음으로 알고리즘 풀이를 쓰고 있습니다.

스스로를 돌대라기라고 생각하고 아주 세부적인 개념들까지도 풀어 헤치고 있습니다. 거의 떠먹여 주는 내용이라는 장점이 있지만, 필자 역시도 오개념 혹은 부족한 개념이 있기 때문에 포스팅에(거의 없다고 자부하고 싶지만) 부족한 부분도 있을 것입니다. 그러니까 제 공부의 흔적만 읽지 말고 직접 해보세요! 교과서를 백날 읽어도 본인이 실천안 하면 못 배웁니다. 정적인 사람이라면 읽는 것만으로도 그게 되겠지만 동적 학습이 필요하다면, 본인이 코드를 직접 짜 보고, 더 나은 방법이 있다 하고 저한테 이의제기(Argument)를 달아주는 패기를 보여주신다면 더할 나위 없이 환영입니다.

 

짧은 요약 : 공부는 본인이 하는 거다, 아무리 좋은 참고서라도 안 하면 말짱 도루묵... 부디, 수도(pseudo) 레벨과 code레벨의 알고리즘을 이해하면 스스로 응용할 수 있는 숙제를 풀어보는 정도의 노력은 합시다.

가령 이번 문제가 오름차순(Asending) 정렬(Sort) 이진(Binary) 탐색(Search) 면 개념을 성실히 이해했다면, 착한 어린이라면,  내림차순(Desending) 정렬(Sort) 이진(Binary) 탐색(Search) 정도는 본인이 짜는 노력은 하리라 믿습니다.

 

해도 되고 안 해도 되는 숙제 : 내림차순 이진 탐색을 한번 구현해 보세요, 물론 L, M, H를 모두 x랑 비교해서 리턴하는 방식으로 해도 됩니다.

 

내 글을 제대로 정독하고 이해하고 넘어갔다면, 컴퓨터에 언어를 하나라도 아는 중학생이라도, 풀 수 있는 숙제입니다. 데이터 여러 개를 집합체로 구현 가능하며 정렬 알고리즘을 구현할 수 있는 모든 언어라면 구현 가능한 너무나 쉬운 모든 알고리즘의 가장 기초입니다. 그러니까 변명 그만하고 제발 직접 구현 ㄱㄱㄱ!