이진탐색 | 재귀
Algorithm 2019. 8. 30. 12:20반응형
[탐색 알고리즘] 이진 탐색 알고리즘(Binary Search)
[탐색 알고리즘] 이진 탐색 알고리즘(Binary Search) 이진 탐색 알고리즘 이진 탐색 알고리즘을 위해서는 데이터가 정렬되어 있어야 한다. 이진 탐색 알고리즘은 정렬된 데이터가 아니면 적용이 불가능하다. 배열..
ledgku.tistory.com
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
|
using System;
namespace Application
{
class MainClass
{
public static void Main(string[] args)
{
Console.WriteLine("Hello World!");
int[] arr = { 1, 3, 5, 11, 24 };
var sol = new Solution();
//sol.solution(arr, 11);
sol.solution2(arr, 11);
}
}
public class Solution {
public void solution(int[] arr, int target) {
int start = -1;
int end = length;
//엇갈릴때까지
while (start + 1 < end) {
int mid = (start + end) / 2;
//타겟과 비교
if (arr[mid] < target)
{
//오른쪽에 있음
start = mid; //시작지점을 중간으로 잡음 (중간 ~ 끝)
}
else
{
//왼쪽에 있음
end = mid; //시작 지점을 끝으로 잡은 (시작 ~ 중간)
}
}
Console.WriteLine("index: {0}, value: {1}", end, arr[end]);
}
public void solution2(int[] arr, int target) {
int start = -1;
solution2_recursive(arr, target, start, end);
}
private int solution2_recursive(int[] arr, int target, int start, int end) {
int mid = (start + end) / 2;
if (arr[mid].Equals(target))
{
Console.WriteLine("idx: {0}, val: {1}", mid, arr[mid]);
return mid;
}
else
{
if (arr[mid] > target)
{
end = mid - 1;
solution2_recursive(arr, target, start, end);
}
else
{
start = mid + 1;
solution2_recursive(arr, target, start, end);
}
}
return -1;
}
}
}
|
반응형
'Algorithm' 카테고리의 다른 글
| 재귀 | n까지의 합 (0) | 2019.08.30 |
|---|---|
| 선택 정렬 (0) | 2019.08.30 |
| 소수구하기 | Prime Number | 에라토스테네스의 체 (0) | 2019.08.30 |
| LeetCode | Easy | Reverse Integer (0) | 2019.08.29 |
| LeetCode | Easy | Palindrome Number | 팰린드롬 (0) | 2019.08.29 |