Programmin Challenge: the position of the element (Messing around in Swift)

gistfile1.swift

import UIKit

// binary search function to find position
func findPositionInArray<T: Comparable>(array: [T], value: T) -> Int {
    var lowerIndex = 0
    var upperIndex = array.count - 1
    
    while lowerIndex < upperIndex {
        let currentIndex = lowerIndex + Int(Double(upperIndex - lowerIndex) * 0.5)
        let currentValue = array[currentIndex]
        
        // if equal then return index
        if currentValue == value {
            return currentIndex
        }
        
        // if not found then calculate where it should be
        if (lowerIndex == upperIndex - 1) {
            if value <= array[lowerIndex] {
                return lowerIndex
            } else if value <= array[upperIndex] {
                return upperIndex
            } else {
                return upperIndex + 1
            }
        }
        
        // reduce search range
        if currentValue <= value {
            lowerIndex = currentIndex
        } else {
            upperIndex = currentIndex
        }
    }
    
    return -1
}

// generate random array
let arraySize = 10
let maxNumber: UInt32 = 100

var array: [Int] = []

for i in 0..<arraySize {
    array.append(Int(arc4random_uniform(maxNumber)))
}

// sort it
array.sort{$0 < $1}

// generate random search value
let findValue = Int(arc4random_uniform(maxNumber))

// run the function
let result = findPositionInArray(array, findValue)

println("Array = \(array)")
println("FindValue = \(findValue)")
println("\nResult = \(result)")

// run in O(logn) time and n space

if result > 0 {
    println("\nIndex \(result - 1) = \(array[result - 1])")
}

if (result < array.count) {
    println("Index \(result) = \(array[result])")
}

if (result + 1 < array.count) {
    println("Index \(result + 1) = \(array[result + 1])")
}

Nice job!

Removed the while true and added better loin for the result 😃

Array = [10, 14, 33, 40, 63, 65, 71, 71, 80, 99]
FindValue = 77

Result = 8

Index 7 = 71
Index 8 = 80
Index 9 = 99