14 Sep 2020 . 2 min read @gurjitpt
In computer science, there are two types of algorithms commonly used to solve a problem searching and sorting algorithms. Its valuable to know which algorithm to use to perform a computation.In this tutorial, we will focus on searching algorithms.
When we talk about searching algorithms the use of binary search algorithm is very common. It is a very simple algorithm used to find a value within a sorted array.
In binary search, we find specific value in sorted array by comparing that value to mid element of array. If value matches the mid element of array it returns the position from array. If value is less than mid element of array, then we search the left half of array. If value is greater than mid element of array, then we search the right half of array. We repeat this process until we either find a target or if subarray size is 0 then value is not in array.
Now we will implement binary search step by step.
1. First of all, choose sorted array to search for
var arrayToSearch = [2,5,8,9,10,12,16]
2. Now choose target value to search in sorted array
var valueToFind = 10
3. Set low index and highIndex
var lowIndex = 0
var highIndex = arrayToSearch.count - 1
4. Create a function for performing binary search with two parameters, array of type [Int] and key of type Int. The function has return type Int? an optional type
func binarySearch(array:[Int], key: Int) -> Int? {
}
5. Now we will iterate over array using while loop. It will iterate until lowIndex is lower or equal than highIndex
while lowIndex <= highIndex {
}
6. Set position of middle element of array
let mid = (lowIndex + highIndex) / 2
7. If mid element of array matches target key than return mid element position
if array[mid] == key {
return mid
}
8. If mid element of array less than target key than set lowIndex to mid + 1
else if array[mid] < key {
lowIndex = mid + 1
}
9. If mid element of array greater than target key than set highIndex to mid - 1
else {
highIndex = mid - 1
}
10. If target key doesn't matches any element from array it will return nil
return nil
Finally, perform binary search operation by calling binarySearch function. If target value found display message that value found at that position or otherwise if it returns nil display value not found.
var result = binarySearch(array: arrayToSearch, key: valueToFind)
if (result != nil) {
print("Value found at \(result ?? 0)")
} else {
print("Value not found")
}
import UIKit
var arrayToSearch = [2,5,8,9,10,12,15]
var valueToFind = 10
var lowIndex = 0
var highIndex = arrayToSearch.count - 1
func binarySearch(array:[Int], key: Int) -> Int? {
while lowIndex <= highIndex {
let mid = (lowIndex + highIndex) / 2
if array[mid] == key {
//print("Value found")
return mid
} else if array[mid] < key {
lowIndex = mid + 1
} else {
highIndex = mid - 1
}
}
return nil
}
var result = binarySearch(array: arrayToSearch, key: valueToFind)
if (result != nil) {
print("Value found at \(result ?? 0)")
} else {
print("Value not found")
}
It is very important to know which algorithm to be use to solve a problems or to perform a computation.Binary search algorithm is faster than another searching algorithms when array is larger in size. Binary search only can be apply when array is sorted.
Don’t hesitate to contact me if you have any questions or queries. Follow me on twitter @gurjitpt for any updates.
Thanks!
WRITTEN BY
Gurjit Singh
I’m Computer Science graduate and an iOS Engineer who writes about Swift and iOS development. Follow me on twitter @gurjitpt for more updates.
Enumerations (enum) enables you to write code in a type safe way. Enum is very useful while defining common type of values. You don't have to provide...
Mar 7, 2023 . 2 min read Swift Enum
Optional unwrapping is one of the most used patterns in iOS development. Swift 5.7 introduces new features included a new way to unwrap optional values...
Jun 14, 2022 . 2 min read Optional unwrapping
It's a common pattern or technique in various programming languages when we want to perform some action when a value is changed. Property ...
May 24, 2021 . 2 min read Property Observers