Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Programmin Challenge: the position of the element (Messing around in 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])")
}
@oliverfoggin

This comment has been minimized.

Copy link
Owner Author

commented May 25, 2015

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

@svpino

This comment has been minimized.

Copy link

commented May 25, 2015

Nice job!

@oliverfoggin

This comment has been minimized.

Copy link
Owner Author

commented May 26, 2015

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.