Binary-Search

Binary Search in Swift.

Wikipedia: In computer science, binary search, also known as half-interval search, logarithmic search, or binary chop, is a search algorithm that finds the position of a target value within a sorted array.

Binary search algorithm runtime of O(log n) has a more optimal runtime due to its use of divide and conquer as opposed to linear search O(n) which visits each element during search. Runtimes shown in the Big O chart below.

1. Linear Search

func linearSearch(_ arr: [Int], _ target: Int) -> Int {
  for (index, num) in arr.enumerated() { // for loop runs O(n) times e.g 15 times if 16 elements and target is last
    if num == target {
      return index
    }
  }
  return -1
}

linearSearch([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16], 16) // index 15 returned

In the above linearSearch function the runtime is O(n). Worst case searching a million elements, we would have to iterate through a million elements. 😱

2. Binary Search

func binarySearch(_ arr: [Int], _ target: Int) -> Int {
  var low = 0
  var high = arr.count
  while low < high { // while loop runs O(log n) times e.g will be 4 times, worst case target is the last of 16 elements
    let middleIndex = low + (high - low) / 2
    if arr[middleIndex] == target {
      return middleIndex
    } else if arr[middleIndex] > target { // go left
      high = middleIndex
    } else { // go right
      low = middleIndex + 1
    }
  }
  return -1
}

binarySearch([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16], 16) // index 15 returned

In the binarySearch function above the runtime is drastically faster as we are using a divide and conquer algorithm and cutting the problem in half on every iteration. Our runtime is logorithmic at O(logn) . Worst case searching a million elements, we would have to iterate 20 times, yep 20. 🥳 🤯 Binary search wins...linear would be 1 million times in the worst case scenario that the target element is last in the collection.

Try it here using a log calculator

Challenges

Challenge 1 - Convert the binary search solution to be a generic function that works with any type

func binarySearch(_ nums: [Int], _ target: Int) -> Int {
  var low = 0
  var high = nums.count
  
  while low < high {
    let middleIndex = low + (high - low) / 2 // divide in half each time => O(log n)
    if nums[middleIndex] == target {
      return middleIndex
    } else if nums[middleIndex] > target { // look left
      high = middleIndex
    } else { // look right
      low = middleIndex + 1
    }
  }
  return -1
}

binarySearch([-6, 2, 5, 9, 11, 45, 78], 2) // index 1 returned

Challenge 2 - Binary Search

LeetCode

Challenge 3 - First bad version

LeetCode

Challenge 4 - Write binary search using recursion

Write binary search using recursion

Resources

1. Wikipedia - Binary Search
2. GeeksForGeeks
3. Google AI Blog - bug solved in large array search
4. Log Calculator