Binary Search Algorithm (Must be sorted!)

binary_search.swift

extension Int {
  var asDouble: Double {
    return Double(self)
  }
}

extension Double {
  var halve: Double {
    return self / 2
  }
  var asInt: Int {
    return Int(self)
  }
}

func binary_search(_ nums: [Int], n: Int) -> Bool {
  let midIndex = (nums.count - 1).asDouble.halve.rounded().asInt

  // midIndex == Nums.count - 1 && n != nums[midIndex]: Mid index and amount of elements is the same and the number doesn't equal that one single element
  // OR the midindex is smaller than 0, in that case that means the item that is being looked for is smaller than the smallest item in the array
  // and thus doesn't exist

  if midIndex == nums.count - 1 && n != nums[midIndex] || midIndex < 0 { return false }

  let leftRange = 0..<midIndex
  let rightRange = midIndex..<nums.count

  if n == nums[midIndex] { return true }
  if n < nums[midIndex] { return binary_search(Array(nums[leftRange]), n: n) }

//  => if n > nums[midIndex]
  return binary_search(Array(nums[rightRange]), n: n)
}