Search algorithms that are used to retrieve information from a data structure, in this post I'll describe 3 search algorithms to find an element in lists.
Linear Search
Linear search is the most basic and easier to understand search algorithm, it simply starts from the first element in the list, and check each element to see if it is the element we are searching for, if the element is found returns its position in the list, else returns -1, null or undefined. Since it goes through the entire list, its time complexity is O(n).
1function linearSearch(list:number[], n:number): number {
2 for(let i=0; i< list.length; i++) {
3 if(list[i] === n) return i
4 }
5}
6
7const list = [2,6,4,8,9,0,1,5]
8console.log(linearSearch(list, 1)) // 6
What if we are given a sorted list? The next two algorithms work on sorted lists and are faster than the Linear Search algorithm.
Jump Search
Instead of check element-by-element, This algorithm search block-by-block, so it checks fewer elements.
- We start defining a block size
- Starting from the beginning of the list, we check the last element of each block, if the element is smaller than the value we are looking for, we jump to the next block.
- But, if the last element of the current block is greater than the value we are looking for, we do a linear search in that block.
Jump Search time complexity in the average and worst cases is O(√ n).
1function jumpSearch(list:number[], n:number): number {
2 const blockSize = Math.floor(Math.sqrt(list.length))
3 const start = 0
4
5 while(list[start+blockSize-1] < n) {
6 if(start + blockSize >= list.length) {
7 start += list.length - 1 - start
8 }else {
9 start += blockSize
10 }
11 }
12
13 for(let i=start; i < start+blockSize-1; i++) {
14 if(list[i] === n) return i
15 }
16}
17
18const sortedList = [1,2,3,4,5,6,7,8,9,10]
19console.log(jumpSearch(sortedList, 5)) // 4
Binary Search
This algorithm is also meant for sorted lists, it uses a divide-and-conquer technique, which means it divides the problem into smaller parts that are easier to solve.
- Start by checking the element in the middle of the lists, if this element is the element we are searching for returns its position.
- If that middle element is greater than the element we are searching for, repeat the first step for the right half.
- But, if that middle element is smaller, repeat the first step for the left half.
Notice that this algorithm keeps dividing the sublists into even smaller ones checking only the element in the middle of each sublist, and it might, eventually, wind up with a sublist that contains a single element. Since this algorithm is halving the list at each iteration its time complexity is O(log n).
Worth mentioning that this algorithm is also implemented for a Binary Search Tree.
Here's an recursive implementation of Binary Search without any auxiliary data structures:
1function binarySearch(list:number[], n:number, low:number, high:number): number {
2 // base case
3 if(low > high) return
4
5 let middle = Math.floor((low + high) / 2)
6
7 if(list[middle] === n) return middle
8
9 if(n < list[middle]) return binarySearch(list, n, low, middle-1)
10
11 if(n > list[middle]) return binarySearch(list, n, middle+1, high)
12}
13
14const sortedList = [1,2,3,4,5,6,7,8,9,10]
15console.log(binarySearch(sortedList, 3, 0, sortedList.length - 1))
