Luiz GabrielWe 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
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 <= 104104 < nums[i], target < 104- All the integers in
numsare unique. -
numsis 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
Contact Me:
