BinarySearch

BinarySearch

import Foundation

// Binary search using simple function
func binSearch (list: [Int], value: Int) -> Int?{
    
    if !list.isEmpty{
        var indexMin = list.startIndex
        var indexMax = list.endIndex-1
        
        while indexMin <= indexMax{
            
            let indexMid = indexMin + (indexMax - indexMin)/2
            
            if list[indexMid] == value{
                return indexMid
            }
            
            if value < list[indexMid]{
                indexMax = indexMid-1
            }
            else{
                indexMin = indexMid+1
            }
        }
    }
    return nil
}

// Binary search using recursive function
func binarySearchRecursion(element: Int, in array: [Int]) -> Int? {
    var startIndex = 0
    var endIndex = array.count - 1
    let middle = Int((startIndex + endIndex) / 2)
    
    if !array.isEmpty {
        if array[middle] == element {
            return element
        } else if array.count == 1 {
            return nil
        }
        
        if array[middle] < element {
            startIndex = middle + 1
        } else if array[middle] > element {
            endIndex = middle - 1
        }
        
        let subArray = Array(array[startIndex...endIndex])
        return binarySearchRecursion(element: element, in: subArray)
    } else {
        return nil
    }
}

// Helper method to get elapsed time
func printTimeElapsedWhenRunningCode(title: String, operation:()->()) {
    let startTime = CFAbsoluteTimeGetCurrent()
    operation()
    let timeElapsed = (CFAbsoluteTimeGetCurrent() - startTime) * 1000
    let value = String(format: "%.2f ms.", timeElapsed)
    print("Time elapsed for \(title): \(value)")
}

let array100Elements = Array(0...99)
let array10000Elements = Array(0...9_999)
let a = 51
let b = 5001

printTimeElapsedWhenRunningCode(title: "Simple loop search with \(array100Elements.count) elements") {
    for item in array100Elements {
        if item == a {
            break
        }
    }
}

printTimeElapsedWhenRunningCode(title: "Simple loop search with \(array10000Elements.count) elements") {
    for item in array10000Elements {
        if item == b {
            break
        }
    }
}

print(" \n*********************************\n ")

printTimeElapsedWhenRunningCode(title: "Functional search with \(array100Elements.count) elements") {
    _ = array100Elements.filter({ $0 == a })
}

printTimeElapsedWhenRunningCode(title: "Functional search with \(array10000Elements.count) elements") {
    _ = array10000Elements.filter({ $0 == b })
}

print(" \n*********************************\n ")

printTimeElapsedWhenRunningCode(title: "BinarySearch (simple) with \(array100Elements.count) elements") {
    _ = binSearch(list: array100Elements, value: a)
}

printTimeElapsedWhenRunningCode(title: "BinarySearch (simple) with \(array10000Elements.count) elements") {
    _ = binSearch(list: array10000Elements, value: b)
}

print(" \n*********************************\n ")

printTimeElapsedWhenRunningCode(title: "BinarySearch (recursive) with \(array100Elements.count) elements") {
    _ = binarySearchRecursion(element: a, in: array100Elements)
}

printTimeElapsedWhenRunningCode(title: "BinarySearch (recursive) with \(array10000Elements.count) elements") {
    _ = binarySearchRecursion(element: b, in: array10000Elements)
}