Data Structures & Algorithms in Swift · Challenge: Binary Search | raywenderlich.com

Official Tutorials
1
This is a companion discussion topic for the original entry at https://www.raywenderlich.com/977854-data-structures-algorithms-in-swift/lessons/14
2

My Binary Search Challenge was this:

func findRange(of value: Int, in array: [Int]) -> CountableRange<Int>? {
  guard let i = array.binarySearch(for: value) else { return nil }
  var leftIndex = i
  var rightIndex = i
  
  repeat {
    leftIndex -= 1
  } while (leftIndex > 0 && array[leftIndex - 1] == value)

  repeat {
    rightIndex += 1

  } while (rightIndex < array.count - 1 && array[rightIndex] == value)
  
  return leftIndex..<rightIndex
}

It’s tested and works very well :smile:. But is it considered binary search?

3

Oh, interesting! I like how you started with the binary search we already wrote. Right now, after you get that initial index for a matching value, you’re doing a linear search in two directions.

Which, like you said, works just fine! But I think to make the whole thing a binary search you’d need to continue finding middle indices and searching from there in each of your loops. I suspect you could continue using the original binarySearch on new arrays, built in both directions from i.

4

This challenge and the binary tree serialization challenge seem like a steep jump in difficulty from the stack and queue challenges.

5

@inquen Please let us know what you don’t understand exactly when you get a chance. Thank you!