-2

Imagine I have the following two arrays: 

let array1 = [1,4,6,9,12,18]
let array2 = [6,9,4,18,12,1]

Now I want to find the index of 9

array1.index(of:9) // 3
array2.index(of:9) // 1

Is there anyway to tell the compiler like "Unlike array2, where you need to look up all the indexes one by one, array1 is already sorted, so you can save time and do a binarySearch"

maybe something like:

array1.index(of : 9, isSorted : true)
array2.index(of : 9, isSorted : false)
sepp2k
  • 363,768
  • 54
  • 674
  • 675
mfaani
  • 33,269
  • 19
  • 164
  • 293
  • Also related [How do I insert an element at the correct position into a sorted array in Swift?](https://stackoverflow.com/questions/26678362/how-do-i-insert-an-element-at-the-correct-position-into-a-sorted-array-in-swift/26679191#26679191) – mfaani Nov 06 '18 at 15:20

1 Answers1

1

Nope. But you can implement it yourself.

In principle, Array could have been implemented to manage this automatically. It could have a isSorted flag, that's set by default for an empty array, reset anytime a sort-order-violating operation is done, and set anytime sort is called. Then, any functions that have more optimal implementations for sorted data can check against this flag, doing either the optimized or general algorithm, as required.

However, I suspect that the cost of such book-keeping (paid by almost all operations), will outweigh the limited benefit (reaped by only some operations).

Alexander
  • 59,041
  • 12
  • 98
  • 151
  • 4
    see https://stackoverflow.com/questions/31904396/swift-binary-search-for-standard-array for pointers – leonardkraemer Nov 06 '18 at 00:36
  • 1) That's bad. I mean assume I get a sorted array from server and now want to do a search operation on it. It would be great if I can inform the compiler that it's already sorted. 2) Assuming an array is not sorted. What Swift does is that it just goes steps through the array index by index. Is that correct? – mfaani Nov 06 '18 at 00:42
  • 1
    @Honey The compiler is far removed from your running app. – rmaddy Nov 06 '18 at 00:49
  • Right. Thanks for the correction. Let me rephrase: if I can give some flag to switch against and change the flow on how to do the sorting. Not sure how exactly I should edit the original question. Can you edit it please? – mfaani Nov 06 '18 at 00:53
  • 1
    @Honey If you don't care about the ordering of these items, you can use a `[Int: Item]` instead of an `[Item]`, which grants you `O(1)` search, insertion and deletion. – Alexander Nov 06 '18 at 02:24
  • The way you put...I guess for every collection variable in my interviews I should be asking myself that question. Thanks – mfaani Nov 06 '18 at 02:52
  • @Honey Well it depends on how often you'll be searching, and by what properties. Sometimes a database is more appropriate, to allow for multiple indexes over the same data. – Alexander Nov 06 '18 at 17:48
  • _to allow for multiple indexes over the same data_ not following. Can you elaborate? – mfaani Nov 06 '18 at 20:00