Binary Search?
이진 탐색(Binary Search)은 정렬된 배열에서 값을 효율적으로 찾기 위한 알고리즘입니다. 이진 탐색은 배열을 절반으로 나누어 타겟 값이 어느 절반에 있는지 결정하고, 그 절반에서 다시 절반으로 나누는 과정을 반복합니다. 이 방식으로 탐색 범위를 빠르게 좁힐 수 있어 O(log n)의 시간 복잡도를 가집니다.
사용 사례:
- 정렬된 데이터: 이진 탐색은 반드시 데이터가 정렬되어 있어야 합니다.
- 대규모 데이터: 큰 데이터 세트에서 빠르게 검색해야 할 때 매우 유용합니다.
- 효율적인 탐색 필요: 선형 탐색(Linear Search)의 O(n) 시간 복잡도에 비해 훨씬 효율적이므로, 성능을 최적화할 때 자주 사용됩니다.
JavaScript 예제 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function binarySearch(arr, target) {
let left = 0;
let right = arr.length - 1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (arr[mid] === target) {
return mid; // 타겟 값을 찾은 경우 인덱스 반환
} else if (arr[mid] < target) {
left = mid + 1; // 오른쪽 절반에서 탐색
} else {
right = mid - 1; // 왼쪽 절반에서 탐색
}
}
return -1; // 타겟 값을 찾지 못한 경우
}
// 사용 예시
const arr = [1, 3, 5, 7, 9, 11, 13, 15];
const target = 9;
console.log(binarySearch(arr, target)); // 4 (타겟 9의 인덱스)
설명:
binarySearch함수는 정렬된 배열arr에서 값target을 찾습니다.- 배열을 절반으로 나누어 탐색하며, 중간값과 타겟 값을 비교한 후 오른쪽 또는 왼쪽 절반에서 다시 탐색합니다.
Rust 예제 코드
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
fn binary_search(arr: &[i32], target: i32) -> Option<usize> {
let mut left = 0;
let mut right = arr.len() as i32 - 1;
while left <= right {
let mid = left + (right - left) / 2;
if arr[mid as usize] == target {
return Some(mid as usize); // 타겟 값을 찾은 경우 인덱스 반환
} else if arr[mid as usize] < target {
left = mid + 1; // 오른쪽 절반에서 탐색
} else {
right = mid - 1; // 왼쪽 절반에서 탐색
}
}
None // 타겟 값을 찾지 못한 경우
}
fn main() {
let arr = [1, 3, 5, 7, 9, 11, 13, 15];
let target = 9;
match binary_search(&arr, target) {
Some(index) => println!("Found at index: {}", index),
None => println!("Not found"),
}
}
설명:
binary_search함수는 Rust에서 정렬된 배열arr내의 값target을 찾습니다.- 배열을 절반으로 나누고, 타겟 값이 중간값보다 큰지 작은지에 따라 탐색 범위를 좁혀가며 값을 찾습니다.
요약:
이진 탐색은 정렬된 배열에서 값의 위치를 찾는 매우 효율적인 알고리즘으로, O(log n)의 시간 복잡도를 가집니다. 정렬된 데이터를 빠르게 검색할 수 있어 대규모 데이터 세트에서 유용하며, 효율적인 탐색이 필요한 경우에 많이 사용됩니다.
Binary Search Explanation?
Binary Search is an algorithm used to efficiently find values in a sorted array. It works by dividing the array in half and determining which half the target value is in, then repeating the process in that half. This method allows for rapid narrowing of the search space, resulting in a time complexity of O(log n).
Use Cases:
- Sorted Data: Binary Search can only be applied when the data set is sorted.
- Large Data Sets: It is very useful when you need to quickly search through large datasets.
- Efficient Search Requirement: Compared to linear search, which has a time complexity of O(n), binary search is much more efficient, making it a common choice for performance optimization.
JavaScript Example Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function binarySearch(arr, target) {
let left = 0;
let right = arr.length - 1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (arr[mid] === target) {
return mid; // Return index if target value is found
} else if (arr[mid] < target) {
left = mid + 1; // Search in the right half
} else {
right = mid - 1; // Search in the left half
}
}
return -1; // Return -1 if target value is not found
}
// Example usage
const arr = [1, 3, 5, 7, 9, 11, 13, 15];
const target = 9;
console.log(binarySearch(arr, target)); // Output: 4 (index of target 9)
Explanation:
- The
binarySearchfunction searches for thetargetvalue in a sorted arrayarr. - It divides the array in half and compares the middle value with the target, narrowing the search to either the right or left half based on the comparison.
Rust Example Code
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
fn binary_search(arr: &[i32], target: i32) -> Option<usize> {
let mut left = 0;
let mut right = arr.len() as i32 - 1;
while left <= right {
let mid = left + (right - left) / 2;
if arr[mid as usize] == target {
return Some(mid as usize); // Return index if target value is found
} else if arr[mid as usize] < target {
left = mid + 1; // Search in the right half
} else {
right = mid - 1; // Search in the left half
}
}
None // Return None if target value is not found
}
fn main() {
let arr = [1, 3, 5, 7, 9, 11, 13, 15];
let target = 9;
match binary_search(&arr, target) {
Some(index) => println!("Found at index: {}", index),
None => println!("Not found"),
}
}
Explanation:
- The
binary_searchfunction in Rust checks a sorted arrayarrfor thetargetvalue. - It divides the array in half and narrows the search space based on comparisons with the middle value.
Summary:
Binary Search is a highly efficient algorithm for finding values in a sorted array, with a time complexity of O(log n). It can quickly search through sorted data, making it very useful for large datasets and often used when efficient searching is necessary.