We have the following scenario: We have been given the task of searching for the Product red water bottle in a supermarket stock, in this stock there are 10,000 registered products.

What is Linear Search?

• It's a simple search algorithm that searches element by element sequentially, with the first element having index 0.
• Imagine that it takes 1 second to go through each element and the desired product is in position 4,500, this would take 1:15h to find. A totally unfeasible process.
• In large lists, the cost is higher the maximum number of attempts is equal to the size of the list.
• execution time O(n) -> Execution time increases linearly with the size of the data input.

import Foundation

func linearSearch(array: [Int], key: Int) -> Int? {
    for index in 0..< array.count {
        if array[index] == key {
            return index
        }
    }
    return nil
}


let numbers = [5, 3, 8, 1, 2, 9, 4, 10 , 11]
if let index = linearSearch(array: numbers, key: 9) {
    print("Item found in the index \(index)")
} else {
    print("Item not found")
}

What is Binary Search?

This data structure has some characteristics such as:

• To use it, the list must be sorted; if it is not sorted, you can use a sorting algorithm.
• execution time O(log n) -> n is the number of elements in the list Many frameworks already have this implemented.
• To calculate the number of attempts, log2(n) is used.
• The first step is to define the highest point, the lowest point and the middle.

Left = 0 (start of array)

Right = array size minus 1

*Middle = (left + right) / 2 (always integer division)
*

OBSERVATIONS:

• if left and right meet, the target does not exist in the array

• if middle > target then right will swap places and go to a position before middle

• if middle < target then left will swap places and move to a position after middle

• if the middle is equal to the target, we find the result

Suppose you want to find the number 100 in the array below:

Set the initial values of the lower, higher and middle points

left = 0
right = array.count - 1 (7)
middle = (left + right) / 2 (3)

Our target is 100, so we compare the middle with the target:

• middle < target, then we take the left and drag it 1 position in front of the middle

left = 4
right = array.count - 1 (7)
middle = (left + right) / 2 (5)

• we'll do the checks and assignments again until we find the target

• middle == target
  

left = 5
middle = (left + right) / 2 (6)
right = array.count - 1 (7)

When not to use Binary search:

• List with little data, use linear search to avoid over-engineering

• If you need to access the data sequentially, it's better to choose another strategy to apply.

• If the list has a lot of deletions and insertions, it will be difficult to use because you will always need to sort it.

• Where the data is distributed in several places

Leetcode Example

704. Binary Search

Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.

You must write an algorithm with O(log n) runtime complexity.

Example 1:

Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 exists in nums and its index is 4
Example 2:

Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1
Explanation: 2 does not exist in nums so return -1

Constraints:

• 1 <= nums.length <= 104
• 104 < nums[i], target < 104
• All the integers in nums are unique.
• nums is sorted in ascending order.

Answer

func search(_ nums: [Int], _ target: Int) -> Int {
    var left = 0
    var right = nums.count - 1

    // will run until left and right meet
    while left <= right {
        var middle = (right + left) / 2

        if nums[middle] == target {
            return middle
        } else if nums[middle] < target {
            // if middle < target, advance to a position in front of middle
            left = middle + 1
        } else {
            // if middle > target, move to a position behind middle
            right = middle - 1
        }
    }
    // if none is found, return -1 
    return -1
}

List Exercises Leetcode

• List: Link
• Repository with my solutions: Link

Contact Me:

• Linkedin