Finding surrounding elements of value in Array

Question

I have an array of CGFloats. I also have an arbitrary value a that can be any CGFloat. My question is, how do I efficiently find which two indices that a is between. As a side note, a will never be below or greater than the minimum or maximum of the Array, so there is no need to worry about that.

For a simplifed example, I may have:

let array: [CGFloat] = [4, 7, 10, 22, 23, 25, 67]

// a can be any random number, this initialization is for the example
let a = 14

// some algorithm that calculates indexes
// code returns index 2 and 3 (or it returns items 10, 22)

I have developed one method involving for loops, however, the larger the list is the more inefficient the code is. Is there any intelligent, and more efficient code out there?

Thanks for all the help :)

A possible solution, `firstIndex(where:)`, and you find the first index where the value is greater than you value (you get that way the upper bound). Then, the lower index, is that index minus 1. — Larme, Sep 28 '20 at 13:25
Related: https://stackoverflow.com/questions/26678362/how-do-i-insert-an-element-at-the-correct-position-into-a-sorted-array-in-swift/55395494#55395494 — vadian, Sep 28 '20 at 14:13

Leo Dabus · Answer 1 · 2020-09-28T15:39:53.777

What you are looking for is called mid binary search. There is many examples out there of this kind of approach Example #2. Note that if you pass a value lower than the first value it will return the start index and a value higher than the last value it will return the last index.

extension Collection where Element: Comparable, Index == Int {
    func binarySearch(_ element: Element) -> Index {
        var low = 0
        var high = count - 1
        while low < high {
            let mid = low + ((high - low + 1) / 2)
            let current = self[mid]
            if current == element {
                return mid
            } else if current < element {
                low = mid
            } else {
                high = mid - 1
            }
        }
        return low
    }
}

let array: [CGFloat] = [4, 7, 10, 22, 23, 25, 67]
let a = 14
let indexA = array.binarySearch(CGFloat(a))  // 2
let indexB = indexA + 1                      // 3

score 0 · Accepted Answer · answered Sep 28 '20 at 13:41

0

if Your array is always sorted use:

let array: [CGFloat] = [4, 7, 10, 22, 23, 25, 67]
let a: CGFloat = 14
if let maxIndex = array.firstIndex(where: { $0 > a }), maxIndex > 0 {
    print("a between \(maxIndex - 1) and \(maxIndex) indexes")
}

answered Sep 28 '20 at 13:41

Kstin

659
1
4
18

Finding surrounding elements of value in Array

2 Answers2