.NET/C# 컨텍스트에서 이진 검색은 무엇이며 어떻게/왜 사용할 수 있습니까?

Question

오늘 Wikipedia에서 처음으로 이진 검색에 대해 읽었으며 표면을 약간 훑어 보았습니다. 그것은 메모리가 부족한 곳에서 컬렉션의 항목을 빠르게 찾는 데 사용되는 것 같습니다.

. NET/C# 컨텍스트에서 사용할 필요가 있습니까? 실제 실제 세계의 소프트웨어를 제작하면서 이들을 사용하십니까?

이 질문이 불쾌 해지면 유감이지만 학생으로서 진정한 질문을하고 싶습니다.

Answer 1

List<T>은 Array과 마찬가지로 BinarySearch 메서드를가집니다. 정렬 된 목록이 있고 요소를 찾아야 할 경우에 사용할 것입니다. 그들은 인덱스를 반환하기 때문에 키보다 작은 가장 큰 요소를 찾는 것처럼 직선 사전으로는 할 수없는 일을 할 수 있습니다.

실세계 소프트웨어에서 이진 검색을 한 곳은 범위 검색을 수행하는 곳입니다. 배송비는 무게 범위에 대해 주어 지므로 0-1 파운드, 1-5 파운드 및 5-10 파운드에 대해 하나의 요금이 부과 될 수 있습니다. List<T>.BinarySearch으로 전화하여 4 파운드를 찾으면 나에게 첫 번째 색인은 4lb보다 높습니다. 나는 1-5lb 범위를 찾을 수 있습니다. 사전은 단지 4 파운드를 찾지 못했다고 말할 것입니다.

일반적으로 정렬 된 데이터의 경우 SortedList 또는 SortedDictionary을 사용하는 것이 좋습니다.

Answer 2

이진 검색은 정렬 된 데이터에서만 작동하므로 정렬 된 C#의 데이터 컬렉션이있는 한 이진 검색을 수행 할 수 있습니다. 가장 좋은 방법은 이미 제공된 구현 (예 : List<T>.BinarySearch())을 사용하는 것이지만 사용중인 특정 컬렉션에 이진 검색 방법이없는 경우 항상 하나를 쓸 수 있습니다.

다음은 라이브러리에 내장 사용 예입니다 :

// An ordered list of ints 
List<int> ints = new List<int>() { 1, 4, 8, 20, 30, 44 }; 

// Search for 5 in the list 
int ix = ints.BinarySearch(8); 

// Display the index the element 8 was found at 
Console.WriteLine(ix); 

그리고 그래, 당신은 확실히 당신이 정렬 된 데이터를 검색 할 때 이진 검색을 사용할 것입니다.

Answer 3

언젠가 (나는 컴퓨터 공학과에서 학생 이었지만) 검색 알고리즘을 사용해야했습니다. 그러한 교과 과정의 결과는 논문이었습니다.

나는 내 블로그에 Quicksort and Binary Search algorithms in C++에 올렸습니다. C++ 코드이지만 이진 검색을 사용하는 방법/이유는 입니다. 또한 이진 검색 알고리즘을 구현하는 방법을 보여줍니다. 샘플 애플리케이션을 제공하므로 직접 테스트 할 수 있습니다.