이진 검색 알고리즘이란 무엇입니까?
바이너리 검색 내에서 목표 값의 위치를 찾는 데 사용되는 검색 알고리즘입니다. 정렬됨 정렬. 목표 값을 찾거나 간격이 비어 있을 때까지 검색 간격을 반으로 반복적으로 나누는 방식으로 작동합니다. 대상 요소와 검색 공간의 중간 값을 비교하여 검색 간격을 절반으로 줄입니다.
데이터 구조에서 이진 검색 알고리즘을 적용하기 위한 조건
이진 검색 알고리즘을 적용하려면:
- 데이터 구조를 정렬해야 합니다.
- 데이터 구조의 모든 요소에 액세스하려면 일정한 시간이 걸립니다.
이진 검색 알고리즘
다음은 이진 검색의 단계별 알고리즘입니다.
- 검색 공간을 다음과 같이 두 부분으로 나눕니다. 중간 인덱스 “mid” 찾기.
- 검색 공간의 중간 요소를 다음과 비교합니다. 열쇠.
- 만약 열쇠 중간 요소에서 발견되면 프로세스가 종료됩니다.
- 만약 열쇠 중간 요소에서 찾을 수 없는 경우 다음 검색 공간으로 사용할 절반을 선택합니다.
- 만약 열쇠 중간 요소보다 작은 경우 왼쪽 측면은 다음 검색에 사용됩니다.
- 만약 열쇠 중간 요소보다 크면 오른쪽 측면은 다음 검색에 사용됩니다.
- 이 과정은 다음까지 계속됩니다. 열쇠 찾거나 전체 검색 공간이 소진되었습니다.
이진 검색 시각화 도구
이진 검색 알고리즘은 어떻게 작동하나요?
이진 검색의 작동을 이해하려면 다음 그림을 고려하십시오.
배열을 고려해보세요 도착[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91}그리고 목표 = 23.
이진 검색 알고리즘을 구현하는 방법은 무엇입니까?
그만큼 이진 검색 알고리즘 다음 두 가지 방법으로 구현할 수 있습니다
- 반복 이진 검색 알고리즘
- 재귀 이진 검색 알고리즘
아래에는 접근 방식에 대한 의사코드가 나와 있습니다.
반복 이진 검색 알고리즘:
여기서는 while 루프를 사용하여 키를 비교하고 검색 공간을 두 부분으로 분할하는 프로세스를 계속합니다.
C++
// C++ program to implement iterative Binary Search
#include
using namespace std;
// An iterative binary search function.
int binarySearch(int arr[], int low, int high, int x)
{
while (low <= high) {
int mid = low + (high - low) / 2;
// Check if x is present at mid
if (arr[mid] == x)
return mid;
// If x greater, ignore left half
if (arr[mid] < x)
low = mid + 1;
// If x is smaller, ignore right half
else
high = mid - 1;
}
// If we reach here, then element was not present
return -1;
}
// Driver code
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);
if(result == -1) cout << "Element is not present in array";
else cout << "Element is present at index " << result;
return 0;
}
기음
// C program to implement iterative Binary Search
#include
// An iterative binary search function.
int binarySearch(int arr[], int low, int high, int x)
{
while (low <= high) {
int mid = low + (high - low) / 2;
// Check if x is present at mid
if (arr[mid] == x)
return mid;
// If x greater, ignore left half
if (arr[mid] < x)
low = mid + 1;
// If x is smaller, ignore right half
else
high = mid - 1;
}
// If we reach here, then element was not present
return -1;
}
// Driver code
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);
if(result == -1) printf("Element is not present in array");
else printf("Element is present at index %d",result);
}
자바
// Java implementation of iterative Binary Search
import java.io.*;
class BinarySearch {
// Returns index of x if it is present in arr[].
int binarySearch(int arr[], int x)
{
int low = 0, high = arr.length - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
// Check if x is present at mid
if (arr[mid] == x)
return mid;
// If x greater, ignore left half
if (arr[mid] < x)
low = mid + 1;
// If x is smaller, ignore right half
else
high = mid - 1;
}
// If we reach here, then element was
// not present
return -1;
}
// Driver code
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, x);
if (result == -1)
System.out.println(
"Element is not present in array");
else
System.out.println("Element is present at "
+ "index " + result);
}
}
파이썬
# Python3 code to implement iterative Binary
# Search.
# It returns location of x in given array arr
def binarySearch(arr, low, high, x):
while low <= high:
mid = low + (high - low) // 2
# Check if x is present at mid
if arr[mid] == x:
return mid
# If x is greater, ignore left half
elif arr[mid] < x:
low = mid + 1
# If x is smaller, ignore right half
else:
high = mid - 1
# If we reach here, then the element
# was not present
return -1
# Driver Code
if __name__ == '__main__':
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", result)
else:
print("Element is not present in array")
기음#
// C# implementation of iterative Binary Search
using System;
class GFG {
// Returns index of x if it is present in arr[]
static int binarySearch(int[] arr, int x)
{
int low = 0, high = arr.Length - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
// Check if x is present at mid
if (arr[mid] == x)
return mid;
// If x greater, ignore left half
if (arr[mid] < x)
low = mid + 1;
// If x is smaller, ignore right half
else
high = mid - 1;
}
// If we reach here, then element was
// not present
return -1;
}
// Driver code
public static void Main()
{
int[] arr = { 2, 3, 4, 10, 40 };
int n = arr.Length;
int x = 10;
int result = binarySearch(arr, x);
if (result == -1)
Console.WriteLine(
"Element is not present in array");
else
Console.WriteLine("Element is present at "
+ "index " + result);
}
}
자바스크립트
// Program to implement iterative Binary Search
// A iterative binary search function. It returns
// location of x in given array arr[l..r] is present,
// otherwise -1
function binarySearch(arr, x)
{
let low = 0;
let high = arr.length - 1;
let mid;
while (high >= low) {
mid = low + Math.floor((high - low) / 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)
high = mid - 1;
// Else the element can only be present
// in right subarray
else
low = mid + 1;
}
// We reach here when element is not
// present in array
return -1;
}
arr = new Array(2, 3, 4, 10, 40);
x = 10;
n = arr.length;
result = binarySearch(arr, x);
if (result == -1)
console.log("Element is not present in array")
else
{
console.log("Element is present at index "
+ result);
}
PHP
// PHP program to implement
// iterative Binary Search
// An iterative binary search
// function
function binarySearch($arr, $low,
$high, $x)
{
while ($low <= $high)
{
$mid = $low + ($high - $low) / 2;
// Check if x is present at mid
if ($arr[$mid] == $x)
return floor($mid);
// If x greater, ignore
// left half
if ($arr[$mid] < $x)
$low = $mid + 1;
// If x is smaller,
// ignore right half
else
$high = $mid - 1;
}
// If we reach here, then
// element was not present
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;
?>
산출
Element is present at index 3
시간 복잡도: 오(로그 N)
보조 공간: 오(1)
재귀 이진 검색 알고리즘:
재귀 함수를 만들고 검색 공간의 중간 부분을 키와 비교합니다. 그리고 결과에 따라 키가 발견된 인덱스를 반환하거나 다음 검색 공간에 대한 재귀 함수를 호출합니다.
C++
#include
using namespace std;
// A recursive binary search function. It returns
// location of x in given array arr[low..high] is present,
// otherwise -1
int binarySearch(int arr[], int low, int high, int x)
{
if (high >= low) {
int mid = low + (high - low) / 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, low, mid - 1, x);
// Else the element can only be present
// in right subarray
return binarySearch(arr, mid + 1, high, x);
}
return -1;
}
// Driver code
int main()
{
int arr[] = { 2, 3, 4, 10, 40 };
int query = 90;
int n = sizeof(arr) / sizeof(arr[0]);
int result = binarySearch(arr, 0, n - 1, query);
if (result == -1) cout << "Element is not present in array";
else cout << "Element is present at index " << result;
return 0;
}
기음
// C program to implement recursive Binary Search
#include
// A recursive binary search function. It returns
// location of x in given array arr[low..high] is present,
// otherwise -1
int binarySearch(int arr[], int low, int high, int x)
{
if (high >= low) {
int mid = low + (high - low) / 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, low, mid - 1, x);
// Else the element can only be present
// in right subarray
return binarySearch(arr, mid + 1, high, x);
}
// We reach here when element is not
// present in array
return -1;
}
// Driver code
int main()
{
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);
if (result == -1) printf("Element is not present in array");
else printf("Element is present at index %d", result);
return 0;
}
자바
// Java implementation of recursive Binary Search
class BinarySearch {
// Returns index of x if it is present in arr[low..
// high], else return -1
int binarySearch(int arr[], int low, int high, int x)
{
if (high >= low) {
int mid = low + (high - low) / 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, low, mid - 1, x);
// Else the element can only be present
// in right subarray
return binarySearch(arr, mid + 1, high, x);
}
// We reach here when element is not present
// in array
return -1;
}
// Driver code
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 is not present in array");
else
System.out.println(
"Element is present at index " + result);
}
}
파이썬
# Python3 Program for recursive binary search.
# Returns index of x in arr if present, else -1
def binarySearch(arr, low, high, x):
# Check base case
if high >= low:
mid = low + (high - low) // 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, low, mid-1, x)
# Else the element can only be present
# in right subarray
else:
return binarySearch(arr, mid + 1, high, x)
# Element is not present in the array
else:
return -1
# Driver Code
if __name__ == '__main__':
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", result)
else:
print("Element is not present in array")
기음#
// C# implementation of recursive Binary Search
using System;
class GFG {
// Returns index of x if it is present in
// arr[low..high], else return -1
static int binarySearch(int[] arr, int low, int high, int x)
{
if (high >= low) {
int mid = low + (high - low) / 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, low, mid - 1, x);
// Else the element can only be present
// in right subarray
return binarySearch(arr, mid + 1, high, x);
}
// We reach here when element is not present
// in array
return -1;
}
// Driver code
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 is not present in arrau");
else
Console.WriteLine("Element is present at index "
+ result);
}
}
자바스크립트
// JavaScript program to implement recursive Binary Search
// A recursive binary search function. It returns
// location of x in given array arr[low..high] is present,
// otherwise -1
function binarySearch(arr, low, high, x)
{
if (high >= low) {
let mid = low + Math.floor((high - low) / 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, low, mid - 1, x);
// Else the element can only be present
// in right subarray
return binarySearch(arr, mid + 1, high, x);
}
// We reach here when element is not
// present in array
return -1;
}
let arr = [ 2, 3, 4, 10, 40 ];
let x = 10;
let n = arr.length
let result = binarySearch(arr, 0, n - 1, x);
if (result == -1)
console.log("Element is not present in array");
else
console.log("Element is present at index " + result);
PHP
// PHP program to implement
// recursive Binary Search
// A recursive binary search
// function. It returns location
// of x in given array arr[low..high]
// is present, otherwise -1
function binarySearch($arr, $low, $high, $x)
{
if ($high >= $low)
{
$mid = ceil($low + ($high - $low) / 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, $low,
$mid - 1, $x);
// Else the element can only
// be present in right subarray
return binarySearch($arr, $mid + 1,
$high, $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;
?>
산출
Element is present at index 3
- 시간 복잡도:
- 최선의 경우: O(1)
- 평균 사례: O(log N)
- 최악의 경우: O(log N)
- 보조 공간: O(1), 재귀 호출 스택을 고려하면 보조 공간은 O(logN)이 됩니다.
- 이진 검색은 신경망 훈련 알고리즘이나 모델에 대한 최적의 하이퍼파라미터 찾기 등 기계 학습에 사용되는 보다 복잡한 알고리즘을 위한 빌딩 블록으로 사용될 수 있습니다.
- 광선 추적이나 텍스처 매핑을 위한 알고리즘과 같은 컴퓨터 그래픽에서 검색하는 데 사용할 수 있습니다.
- 데이터베이스를 검색하는 데 사용할 수 있습니다.
이진 검색의 장점
- 이진 검색은 특히 대규모 배열의 경우 선형 검색보다 빠릅니다.
- 보간 검색이나 지수 검색과 같이 시간 복잡도가 유사한 다른 검색 알고리즘보다 더 효율적입니다.
- 이진 검색은 하드 드라이브나 클라우드와 같은 외부 메모리에 저장된 대규모 데이터 세트를 검색하는 데 매우 적합합니다.
이진 검색의 단점
- 배열이 정렬되어야 합니다.
- 이진 검색을 위해서는 검색 중인 데이터 구조가 연속적인 메모리 위치에 저장되어 있어야 합니다.
- 이진 검색에서는 배열 요소가 비교 가능해야 합니다. 즉, 순서를 지정할 수 있어야 합니다.
이진 검색 알고리즘이란 무엇입니까?
이진 검색은 정렬된 배열 내에서 대상 값의 위치를 찾는 데 사용되는 매우 효율적인 검색 알고리즘입니다. 배열의 정렬 특성을 활용하여 각 비교 후 검색 공간을 절반으로 줄여 시간 복잡성을 오(로그N).
이진 검색 적용 조건
- 정렬된 데이터 구조: 배열이나 데이터 구조는 오름차순이나 내림차순으로 정렬되어야 합니다.
- 지속적인 액세스: 데이터 구조의 모든 요소에 대한 액세스는 일정한 시간이 소요되어야 합니다. 즉, 임의 액세스가 가능합니다.
이진 검색 알고리즘의 작동 방식
- 초기화: 두 개의 포인터로 시작합니다.
low그리고high배열의 첫 번째와 마지막 인덱스를 가리킵니다. - 중간점 찾기: 중간 지수를 계산하고,
mid = low + (high - low) / 2. - 비교하다: 중간 요소를 목표 값과 비교합니다.
- 중간 요소가 대상과 같으면 검색이 성공한 것입니다.
- 대상이 중간 요소보다 작은 경우 검색 범위를 왼쪽 절반으로 좁힙니다.
- 대상이 더 크면 검색 범위를 오른쪽 절반으로 좁힙니다.
- 반복하다: 대상을 찾거나 검색 공간이 소진될 때까지 과정을 반복합니다.
이진 검색 예
배열을 고려해보세요 arr[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91} 그리고 목표값은 23.
- 세트
low = 0그리고high = 9. - 믿다
mid = 4. 중간 요소는16. - 부터
23 > 16업데이트low = 5. - 재계산
mid = 7. 중간 요소는56. - 부터
23 < 56업데이트high = 6. - 재계산
mid = 5. 중간 요소는23. 타겟 발견!
이진 검색 알고리즘 구현
1. 반복 이진 검색
C++ 코드
int 바이너리 검색(int arr[]int 낮음, int 높음, int x) {
동안 (낮음 <= 높음) {
int mid = 낮음 + (높음 – 낮음) / 2;
만약 (arr[mid] == x) 중간을 반환합니다;
만약 (arr[mid] < x) 낮음 = 중간 + 1;
그렇지 않으면 높음 = 중간 – 1;
}
-1을 반환합니다.
}
파이썬 코드
def 바이너리 검색(arr, low, high, x):
낮을 때 <= 높을 때:
중간 = 낮음 + (높음 – 낮음) // 2
도착하면[mid] == 엑스:
중간에 돌아오다
엘리프 아르[mid]
또 다른:
높음 = 중간 – 1
반환 -1
2. 재귀 이진 검색
C++ 코드
int 바이너리 검색(int arr[]int 낮음, int 높음, int x) {
if (높음 >= 낮음) {
int mid = 낮음 + (높음 – 낮음) / 2;
만약 (arr[mid] == x) 중간을 반환합니다;
만약 (arr[mid] > x) return BinarySearch(arr, low, mid – 1, x);
return BinarySearch(arr, mid + 1, high, x);
}
-1을 반환합니다.
}
파이썬 코드
def 바이너리 검색(arr, low, high, x):
높음 >= 낮으면:
중간 = 낮음 + (높음 – 낮음) // 2
도착하면[mid] == 엑스:
중간에 돌아오다
엘리프 아르[mid] > 엑스:
바이너리 검색(arr, low, mid-1, x)을 반환합니다.
또 다른:
바이너리 검색(arr, mid + 1, high, x)을 반환합니다.
반환 -1
시간 복잡도
- 최선의 경우:
O(1)중간 요소가 대상인 경우. - 평균 및 최악의 경우:
O(log N)각 단계마다 검색 공간이 절반으로 줄어들기 때문입니다.
이진 검색의 장점
- 빠르고 효율적: 특히 대규모 데이터 세트의 경우 선형 검색보다 훨씬 빠릅니다.
- 낮은 공간 복잡성: 반복적인 구현은
O(1)공간 복잡성.
이진 검색의 단점
- 정렬된 데이터가 필요합니다: 데이터 구조가 정렬되어야 합니다.
- 비연속 메모리 요구 사항: 연속된 메모리 위치에 있는 데이터에 가장 잘 작동합니다.
자주 묻는 질문(FAQ)
1. 이진 검색이란 무엇입니까?
이진 검색은 검색 공간을 반복적으로 절반으로 줄여 정렬된 배열 내에서 대상 값을 찾는 효율적인 검색 방법입니다.
2. 바이너리 검색은 어떻게 작동하나요?
대상을 중간 요소와 비교하고 비교를 기반으로 검색을 계속할 절반을 결정합니다.
3. 이진 검색의 시간 복잡도는 얼마입니까?
시간복잡도는 O(log N)어디 N 배열의 요소 수입니다.
4. 이진 검색의 전제 조건은 무엇입니까?
배열은 정렬되어야 하며 요소는 비교 가능해야 합니다.
5. 숫자가 아닌 데이터에도 이진 검색을 사용할 수 있나요?
예, 알파벳 순서의 문자열과 같이 정의된 순서가 있는 한 모든 데이터 유형에 사용할 수 있습니다.
이진 검색은 많은 복잡한 알고리즘과 데이터 구조를 뒷받침하는 기본 알고리즘으로, 개발자와 컴퓨터 과학자에게 중요한 도구입니다.
