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])")
}

Output example...

Array = [9, 69, 100, 388, 469, 526, 538, 565, 769, 872, 924, 967, 984, 1347, 1432, 1442, 1745, 1785, 1992, 2088, 2114, 2340, 2342, 2380, 2437, 2486, 2557, 2588, 2654, 2674, 2739, 2937, 2977, 3023, 3173, 3268, 3381, 3501, 3509, 3715, 3801, 3876, 3956, 4085, 4109, 4281, 4536, 4730, 4838, 4851, 5090, 5147, 5208, 5232, 5359, 5397, 5469, 5533, 5579, 5767, 5866, 5966, 6084, 6142, 6176, 6499, 6512, 6546, 6926, 6931, 6968, 6979, 7111, 7442, 7502, 7544, 7820, 7879, 8083, 8173, 8326, 8338, 8339, 8631, 8640, 8652, 9224, 9226, 9320, 9369, 9429, 9645, 9648, 9716, 9802, 9813, 9834, 9852, 9921, 9958]
FindValue = 2923
Result = 31

Index 30 = 2739
Index 31 = 2937
Index 32 = 2977

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