The Power of Binary Search
Tags: algorithms, swift, tutorial, ios
Published: 2024-07-01 01:51:52

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?

![Linear Search](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/wrt79lz0up2jolctbfz5.png)

- 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:
![array](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/l1aei62njelyd6nxdb4s.png)


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

```
left = 0
right = array.count - 1 (7)
middle = (left + right) / 2 (3)
```
![array](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/8cwkshq5tdgmo0iv086m.png)

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)
```
![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/exq12db0mmlw5wn055qy.png)

- 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)
```
![array](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/h905ol9lww0acsecq2l7.png)

---

### 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](https://leetcode.com/problems/binary-search/description/)

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](https://leetcode.com/tag/binary-search/)
- Repository with my solutions: [Link](https://github.com/Luizrebelatto/Exercises-algorithms)

---
Contact Me:
- [Linkedin](https://www.linkedin.com/in/luizgabrielrebelatto/)