프로그램에 바이너리 검색 적용

Question

현재 버블 정렬을 사용하여 파일을 읽고 정렬하는 프로그램이 있습니다. 그러나 나는 값을 찾기 위해 파일을 검색 할 수있는 함수를 구현해야한다. 내가 사용하고자하는 알고리즘은 바이너리 서치 (Binary Search)이지만이를 구현하는 방법은 확실하지 않습니다.

내가 입력 한 값을 검색 할 파일을 선택할 수 있도록하려면 어떻게해야합니까? 일부 위

var fileData = GetFileData(@"Data1/Day_1.txt", @"Data1/Depth_1.txt", 
    @"Data1/IRIS_ID_1.txt", @"Data1/Latitude_1.txt", @"Data1/Longitude_1.txt", 
    @"Data1/Magnitude_1.txt", @"Data1/Month_1.txt", @"Data1/Region_1.txt", 
    @"Data1/Time_1.txt", @"Data1/Timestamp_1.txt", @"Data1/Year_1.txt"); 

는 Main 메서드 이진 검색의

public class FileData 
{ 
    public int File1Value { get; set; } 
    public decimal File2Value { get; set; } 
    public int File3Value { get; set; } 
    public decimal File4Value { get; set; } 
    public decimal File5Value { get; set; } 
    public decimal File6Value { get; set; } 
    public string File7Value { get; set; } 
    public string File8Value { get; set; } 
    public float File9Value { get; set; } 
    public int File10Value { get; set; } 
    public int File11Value { get; set; } 

    public override string ToString() 
    { 
     return String.Format($"{File1Value}|{File2Value}|{File3Value}|{File4Value}|{File5Value}|{File6Value}|{File7Value}|{File8Value}|{File9Value}|{File10Value}|{File11Value}"); 
    } 
} 

public static FileData[] GetFileData(string firstFilePath, string secondFilePath, 
    string thirdFilePath, string fourthFilePath, string fifthFilePath, 
    string sixthFilePath, string seventhFilePath, string eigthFilePath, 
    string ninthFilePath, string tenthFilePath, string eleventhFilePath) 
{ 

    int intHolder = 0; 
    decimal decHolder = 0; 
    float time = 0; 

    // Get a list of ints from the first file 
    var fileOneValues = File 
     .ReadAllLines(firstFilePath) 
     .Where(line => int.TryParse(line, out intHolder)) 
     .Select(v => intHolder) 
     .ToArray(); 

    // Get a list of decimals from the second file 
    var fileTwoValues = File 
     .ReadAllLines(secondFilePath) 
     .Where(line => decimal.TryParse(line, out decHolder)) 
     .Select(v => decHolder) 
     .ToArray(); 

    var fileThreeValues = File 
     .ReadAllLines(thirdFilePath) 
     .Where(line => int.TryParse(line, out intHolder)) 
     .Select(v => intHolder) 
     .ToArray(); 

    var fileFourValues = File 
     .ReadAllLines(fourthFilePath) 
     .Where(line => decimal.TryParse(line, out decHolder)) 
     .Select(v => decHolder) 
     .ToArray(); 

    var fileFiveValues = File 
     .ReadAllLines(fifthFilePath) 
     .Where(line => decimal.TryParse(line, out decHolder)) 
     .Select(v => decHolder) 
     .ToArray(); 

    var fileSixValues = File 
     .ReadAllLines(sixthFilePath) 
     .Where(line => decimal.TryParse(line, out decHolder)) 
     .Select(v => decHolder) 
     .ToArray(); 

    var fileSevenValues = File 
     .ReadAllLines(seventhFilePath) 
     .ToArray(); 

    var fileEightValues = File 
     .ReadAllLines(eigthFilePath) 
     .ToArray(); 

    var fileNineValues = File 
     .ReadAllLines(ninthFilePath) 
     .Where(line => float.TryParse(line, out time)) 
     .Select(v => time) 
     .ToArray(); 

    var fileTenValues = File 
     .ReadAllLines(tenthFilePath) 
     .Where(line => int.TryParse(line, out intHolder)) 
     .Select(v => intHolder) 
     .ToArray(); 

    var fileElevenValues = File 
     .ReadAllLines(eleventhFilePath) 
     .Where(line => int.TryParse(line, out intHolder)) 
     .Select(v => intHolder) 
     .ToArray(); 

    // I guess the file lengths should match, but in case they don't, 
    // use the size of the smaller one so we have matches for all items 
    var numItems = Math.Min(fileOneValues.Count(), fileTwoValues.Count()); 

    // Populate an array of new FileData objects 
    var fileData = new FileData[numItems]; 
    for (var index = 0; index < numItems; index++) 
    { 
     fileData[index] = new FileData 
     { 
      File1Value = fileOneValues[index], 
      File2Value = fileTwoValues[index], 
      File3Value = fileThreeValues[index], 
      File4Value = fileFourValues[index], 
      File5Value = fileFiveValues[index], 
      File6Value = fileSixValues[index], 
      File7Value = fileSevenValues[index], 
      File8Value = fileEightValues[index], 
      //File9Value = fileNineValues[index], 
      File10Value = fileTenValues[index], 
      File11Value = fileElevenValues[index] 
     }; 
    } 

    return fileData; 
} 

코드에서이다 :

코드 (을 정렬로 필요 없음 도움) 파일에서 읽을 및 정렬 할 수 있도록하는 데 사용 :

static int BinarySearch_R(int key, FileData[] fileData, int low, int high) 
{ 
    if (low > high) return -1; 
    int mid = (low + high)/2; 
    if (key == fileData[mid]) 
    { 

     return mid; 
    } 
    if (key < fileData[mid]) 
    { 
     return BinarySearch_R(key, fileData, low, mid - 1); 
    } 
    else 
    { 

     return BinarySearch_R(key, fileData, mid + 1, high); 
    } 
} 

Answer 1

BinarySearch 메서드를 일반화 할 수있는 방법을 찾고있는 것처럼 들리지만 다른 유형의 객체에서도 작동합니다. 난 당신이 일반적으로 게시 된 첫 번째를 변경 한 아래

, 유형 T이 구현 유형으로 제한된다 IComparable<T> (우리는 방법 내부 inputArray의 항목으로 key을 비교할 수 있어야하기 때문에).

이것은 당신이 당신의 파일에 정의 된 유형에 대해 작동합니다 (int, decimal, string 및 float 모든 IComparable을 구현).

/// <summary> 
/// Returns the index of an item in inputArray that matches the value of key 
/// </summary> 
/// <typeparam name="T">The type of objects in the array</typeparam> 
/// <param name="inputArray">An array of items to search</param> 
/// <param name="key">A key item value to search for</param> 
/// <returns>The index of an item that matches key, or -1 if no match is found</returns> 
public static int BinarySearchIterative<T>(T[] inputArray, T key) 
    where T : IComparable<T> 
{ 
    int min = inputArray.GetLowerBound(0); 
    int max = inputArray.GetUpperBound(0); 

    while (min <= max) 
    { 
     int mid = (min + max)/2; 
     int comparison = key.CompareTo(inputArray[mid]); 

     if (comparison == 0) 
     { 
      return mid; 
     } 
     else if (comparison < 0) 
     { 
      max = mid - 1; 
     } 
     else 
     { 
      min = mid + 1; 
     } 
    } 

    return -1; 
}