Binary Search in C++(Recursive and Iterative)

 이진 탐색을 재귀함수, 반복 함수로 c++로 구현해본다. Binary Search by Recursive function in C++

 

 

기본적으로 이진 탐색은 대상을 한 번 비교를 할 때마다 나머지 반을 무시한다.

① x를 가운데 원소와 비교한다.

② x가 가운데 원소와 같을 때, 가운데 index를 반환한다.

③ 만약 x가 가운데 원소보다 클 때, x는 가운데 원소 바로 다음의 오른쪽 subarray에 있을 수 있다.

④ 그렇지 않다면, x는 가운데 값보다 더 작은 것이고, 왼쪽 subarray에서 다시 찾는다.

 

 

 

● Recursive

Binary Search by Recursive function in C++

 

⊙ BinarySearch 함수

-line 6: 오른쪽에 원소가 하나라도 있을 때 반복한다.

-line 8: int형 변수 mid에는 가운데 원소의 인덱스를 저장한다.

-line 11: 만약 배열의 mid번째 인덱스의 값이 찾고자 하는 값인 x와 같다면 mid를 반환한다.

-line 15: 만약 배열의 가운데 값이 x보다 크다면 왼쪽 subarray에 대해서 함수를 다시 호출해서 반복한다.

-line 19: 만약 배열의 가운데 값이 x보다 작다면 오른쪽 subarray에 대해서 함수를 다시 호출해서 반복한다.

-line 23: 오른쪽에 원소가 하나도 없으면 찾고자 하는 값이 배열 안에 없는 것이고 -1을 반환한다.

 

 

⊙ main 함수

-line 28: arr이라는 array에 2, 3, 4, 10, 40의 원소가 있다고 하자

-line 29: arr 안에 있는 전체 원소의 갯수를 arr의 전체 크기를 첫 번째 원소의 크기를 나눠서 구한다.

-line 30: 찾고자 하는 값인 x를 10으로 둔다.

-line 31: result라는 int형 변수에 위에서 선언한 BinarySearch 함수에서 x를 찾은 인덱스를 저장한다.

-line 32: x가 배열에서 몇 번째 index인지 출력한다.

-line 34: 만약 결과가 -1이라면 BinarySearch 함수에서 23번째 줄에서 언급했듯이 배열 안에 찾고자 하는 값이 없는 것이다.

-line 36: 만약 결과가 -1이 아니라면 result값을 출력해서 찾고자 하는 값이 배열의 몇 번째 index에 있었는지 출력한다. 

 

 

 

 

● Iterative

Binary Search by Iterative function in C++

 

⊙ BinarySearch 함수

-line 9: 배열의 시작 주소가 배열의 끝 주소보다 같거나 작을 때 반복한다.

-line 11: int형 변수 mid에는 가운데 원소의 인덱스를 저장한다.

-line 14: 만약 배열의 mid번째 인덱스의 값이 찾고자 하는 값인 x와 같다면 mid를 반환한다.

-line 18: 만약 배열의 가운데 값이 x보다 작다면 배열의 시작 인덱스를 가운데 인덱스 바로 다음으로 바꾼다.

-line 22: 만약 배열의 가운데 값이 x보다 크다면 배열의 시작 인덱스를 가운데 인덱스 바로 전으로 바꾼다.

-line 27: 만약 배열의 시작 주소가 배열의 끝 주소보다 크다면 찾고자 하는 값이 배열 안에 없는 것이고, -1을 반환한다.

 

 

⊙ main 함수

-line 32: arr이라는 array에 2, 3, 4, 10, 40의 원소가 있다고 하자

-line 33: arr 안에 있는 전체 원소의 갯수를 arr의 전체 크기를 첫 번째 원소의 크기를 나눠서 구한다.

-line 34: 찾고자 하는 값인 x를 10으로 둔다.

-line 35: result라는 int형 변수에 위에서 선언한 BinarySearch 함수에서 x를 찾은 인덱스를 저장한다

-line 36: x가 배열에서 몇 번째 index인지 출력한다.

-line 38: 만약 결과가 -1이라면 BinarySearch 함수에서 27번째 줄에서 언급했듯이 배열 안에 찾고자 하는 값이 없는 것이다.

-line 40: 만약 결과가 -1이 아니라면 result값을 출력해서 찾고자 하는 값이 배열의 몇 번째 index에 있었는지 출력한다. 

 

 

 

 

 

참고: https://www.geeksforgeeks.org/c-program-for-binary-search-recursive-and-iterative/