- **Epistemic status:** #evergreen
A search [[Algorithm]] that can find the position of the target value in a sorted array by dividing the results in half every time it checks. The steps of the [[Algorithm]] are as follows:
1. Start with the middle element of the sorted array
2. If the value of the middle element is equal to the target value return the index of the middle element
3. Or if the target value is less than the middle element search in the left half and repeat step 1.
4. Otherwise, search the right half and repeat step 1.
5. If the target value is not found, return -1.
Let’s use an example to understand this a bit better, since it's tricky to visualize. You got a bunch of files in a folder called best friends.
![[Pasted image 20220516093337.png]]
We need to find `Katy.txt` from the group. For this type of search, you will divide the group into two pairs by picking the file that is in the center. Fiona would be the one in the center of the 2 groups. Since Fiona is not the friend we are looking for, we discard it from the temporary list we are making.
![[Pasted image 20220516093433.png]]
Since Fiona was our file that was the one to classify the groups in two pairs, we know the first group is not where Katy is at. We also discard that group. Now we use Ignus as our center point. The letter K is after the letter I. We further divide the group into two groups, discarding Ignus.
![[Pasted image 20220516093452.png]]
We discard that first group due to Ignus telling us the next group is probably where Katy is at. On this next one, we divide the group into two again, and we can tell that Katy is on the second group. We finally found here.
![[Pasted image 20220516093506.png]]
It has a logarithmic time in worse case scenarios of O(log n) and is faster than linear search with the exception of small arrays.
![[Pasted image 20220516093522.png]]
O(log n) Illustration from [The Big O Notation](https://towardsdatascience.com/the-big-o-notation-d35d52f38134)
## Code Snippet
```javascript
/* Returns either the index of the location in the array, or -1 if the array did not contain the targetValue on a sorted array */
function binarySearch(sortedArray, targetValue) {
let min = 0;
let max = sortedArray.length - 1;
let middle;
while(min <= max) {
middle = Math.floor((max + min) / 2);
if (sortedArray[middle] === targetValue) {
return middle;
}
else if (sortedArray[middle] < targetValue) {
min = middle + 1;
}
else {
max = middle - 1;
}
}
return -1;
}
const primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97];
const result = binarySearch(primes, 7);
```
---
## References
- “Big-O Algorithm Complexity Cheat Sheet (Know Thy Complexities!) @ericdrowell.” Accessed June 30, 2022. <https://www.bigocheatsheet.com/>.
- “Binary Search - GeeksforGeeks.” Accessed June 30, 2022. <https://www.geeksforgeeks.org/binary-search/>.
- “Binary Search Algorithm - Wikipedia.” Accessed June 30, 2022. <https://en.wikipedia.org/wiki/Binary_search_algorithm>.
- Stack Abuse. “Binary Search in JavaScript,” October 16, 2020. <https://stackabuse.com/binary-search-in-javascript/>.
- HackerRank. _Algorithms: Binary Search_, 2016. <https://www.youtube.com/watch?v=P3YID7liBug>.