Notice
Recent Posts
Tags
- ATMEGA128A
- normal mode
- 8bit timer/counter
- Algorithm
- atmega 128a
- full adder
- sequential logic circuit
- Method
- structural modeling
- Comparator
- fast pwm mode
- timer / counter
- interrupt
- Linked List
- atmega 128
- verilog
- structure
- Set
- Recursion
- half adder
- 4bit parallel adder
- ctc mode
- java
- interface
- LED
- MUX
- behavior modeling
- dataflow modeling
- behavioral modeling
- gpio
거북이처럼 천천히
Algorithm - Binary search 본문
1. What is binary search?
이진 탐색(Binart search)은 정렬된 배열안에서 특정 값을 찾아내는 알고리즘이다. 배열의 원소들 중에서 중간값을 찾아서 1) 찾고자 하는 값보다 클 경우, 타켓 값은 중간 값을 기준으로 왼쪽에 위치하고, 2) 작을 경우, 타켓 값은 중간 값을 기준으로 오른쪽에 위치한 것을 알 수 있다. 동일한 방법으로 다시 중간의 값을 선택하고 비교한다. 해당 값을 찾을 때까지 이 과정을 반복한다.
2. Example of binary search
List = {1, 2, 3, 4, 5, 6, 7}, Target = {1}
시작점 인덱스는 0, 종점 인덱스는 6일 경우 중간 인덱스는 (시작점 인덱스 + 종점 인덱스) / 2 = 3이다.
- List[3]와 target 값이 같은지 확인했지만, 다르다는 것을 확인하였으며, List[2]가 target보다 크다는 것도 확인했다.
이는 target 값은 중간 인덱스보다 앞에 위치해 있음을 짐작할 수 있다. - 따라서 검색 범위를 [0, 6]에서 [0, 3)로 축소할 수 있다.
List = {1, 2, 3}
시작점 인덱스는 0, 종점 인덱스는 2이며, 중간 인덱스는 (시작점 인덱스 + 종점 인덱스) / 2 = 1이다.
- List[1]와 target 값이 같은지 확인했지만, 다르다는 것을 확인하였으며, List[1]가 target보다 크다는 것도 확인했다.
이는 또 다시 target 값은 중간 인덱스보다 앞에 위치해 있음을 짐작할 수 있다. - 따라서 다시 검색 범위를 [0, 3)에서 [0, 1)으로 축소 할 수 있다.
List = {1}
시작점 인덱스는 0, 종점 인덱스는 0이기 때문에 종점 인덱스는 0이다.
- 드디어 마지막으로 List[0]와 target 값이 동일한지를 확인하였고, 동일함을 확인되어 target 값이 위치한 인덱스를 반환함으로써 해당 메서드는 종료된다.
- 만약 target값이 해당 배열에 존재하지 않다는 것이 확인되면 -1을 반환하는 동시에 프로그램은 종료된다.
3. Binary search source code
3.1. General Infinite Loop
private static int getIndex(int[] list, int begin, int end,int target) {
while(begin<=end) {
int mid = (begin+end)/2;
if(list[mid]==target)
return mid;
else if(list[mid]>target)
begin = mid+1;
else
end = mid-1;
}
return -1;
}
3.2. Recursion
private static int getIndex(int[] list, int begin, int end, int target) {
// ** Base case
if(begin>=end)
return -1;
// ** Recursion case
int mid = (begin+end)/2;
if(list[mid]==target)
return mid;
else if(list[mid]>target)
return getIndex(list, begin, mid-1, target);
else
return getIndex(list, mid+1, end, target);
}
이진 탐색(Binary search)이란 이름이 붙여진 이유는 처음에 N개 크기의 배열에서 단계가 하나씩 지나감에 따라 탐색할 배열의 크기가 반씩 줄어들기 때문이다. 이진 탐색(Binary search)은 정렬된 데이터에서 특정한 값을 찾고자할 때 O (logN)의 성능으로 빠르게 값을 찾을 수 있는 장점이 있다.
'Algorithm > 알고리즘 공부' 카테고리의 다른 글
Java - Sorting algorithm (1) (0) | 2022.10.20 |
---|---|
Algorithm - Recursion의 개념과 기본 예제들 (0) | 2022.10.02 |
Algorithm - Recursion(순환) (0) | 2022.09.28 |
버블정렬(Bubble sort) 알고리즘 (0) | 2022.06.19 |
효율적인 소수 판별법 (0) | 2022.06.18 |