Search is literally a process we undertake everyday as humans, though with different method. We tend to search for a single toy in a pack of toys, books within a bookshelf, picture amongst frames. Searching algorithms tends to check and retrieve an element from a list of element.
We have 2 categories under Searching Algorithm :-
Linear Search: This is a very important aspect of search algorithm, it simply loops over each element in an array, does not care if the array is sorted and stops if that element equals to the target value. In JS, array function such as find(), findIndex(), includes(), indexOf() uses linear search under the hood.
Steps to perform a Linear Search
Linear search takes in an unsorted array and also a target to search for.
Starts checking from the first element in the array till it finds the target.
If it finds the target, stops and then return the target index, if it doesn't it continues till it does and if the target cannot be found, then we return -1 as the return value from the function.
function linearSearch (arr: number[], target: number): number{
for (let i in arr){
if(arr[i] === target) return i
}
return -1
}
console.log(linearSearch([3, 6, 9, 12], 6)) // 0
console.log(linearSearch([2, 4, 6, 8], 9)) // -1
console.log(linearSearch([4, 8, 12, 16, 24], 24)) // 4
Time and Space Complexity for Linear Search
Now that we have understanding on how to perform linear search, we also have to determine the time and space complexity of our linear search function by looking at the best case, average case and worst case, and also space complexity of our code.
Best Case Time Complexity of Linear Search
If the targeted value is place at the beginning of the array list, the linear search function will only be perform a single comparison, irrespective of the number or size of the array. The runtime for this algorithm is a constant time of 0(1).
Average Case Time Complexity
If the targeted value is placed at the mid of the array list, then the complexity will be 0(n/2) simplifying 0(n) or linear time.
Worse Case Time Complexity
When we discover that the targeted value is placed at the end of the array list, then we will have to perform n(length of input array) which makes our time complexity to be linear or 0(n).
Space Complexity of Linear Search
Linear Search has a space complexity of O(1) – constant space.
Binary Search
Unlike linear search method, binary search can only be used to search through ordered list or sorted arrays. Binary search utilizes the divide and conquer method to search for an element by dividing the array into halves, and if the value is found returns the index of the element, if not, returns -1. It is specifically useful for large arrays that are sorted.
Steps to perform a Binary Search.
We start counting the index of the element in the array starting at 0 and dividing by 2 to get the midValue.
Using this midValue, we can then divide the element in the array in half( this is the divide and conquer method).
If the midValue is greater than the target, our search will through the element at the right-hand-side and if lesser than the target, the search will at the left-hand-side because the target will surely be there.
We therefore continue to repeat the process until we find the target.
Example an array of numbers( not prime) with target of 13
[1, 3, 5, 7, 9, 11, 13, 17, 19, 23]
Using this array starting at 1 with index 0, we have 0-9 index.
So the midValue is index 4 which is 9, so we divide into this
[1,2,3,5,7,9] ---- LHS, [11,13,17,19,23] -----RHS
Since target is greater the LHS, we can sinply ignore it and focus of the RHS, then pick the midValue again which is 2( remember we count and divide by index)
[11, 13, 17] --- LHS, [19, 23] ---RHS
Since target is less than the first element in the RHS side array, we can discard the RHS array and focus on the LHS which has our target value at index 1.
CodeXample
We have a function that accepts an array of numbers and a target and returns a number.
function binarySearch(arr: number[], target: number): number {
let startValue : number = 0;
let endValue : number = arr.length -1
let midValue: number = Math.floor((startValue+endValue) /2)
while (arr[midValue] !== target) {
if(target < arr[midValue]){
endValue = midValue - 1
} else {
startValue = midValue + 1
}
midValue = Math.floor((startValue+endValue) /2)
}
if(arr[midValue] === target){
return midValue
}
return -1
}
console.log(binarySearch([2, 5, 6, 9, 13, 15, 28, 30], 9)) // 1
console.log(binarySearch([1, 2, 3, 4, 5], 5)) // 4
console.log(binarySearch([17, 18, 19, 20, 21, 22, 23],22)) // 5
console.log(binarySearch([17, 18, 19, 20, 21, 22, 23],16)) // -1
Time and Space Complexity for Binary Search.
Best Case Time Complexity of Binary Search
The best case complexity of Binary search occurs when the target value is located in the middle of array list. This illustrate that the result will be gotten in constant time irrespective of the size of the array, making the time complexity to be constant time or 0(1).
Average Case Time Complexity
Due to the fact that BS are always sorted unlike LS, the average case is also of O(log(n)).
Worse Case Time Complexity
The worst case complexity of Binary Search occurs when the target value is at the beginning or end of the array.
Space complexity of Binary Search
Binary Search requires three pointers to elements (start, middle and end), regardless of the size of the array. Therefore the space complexity of Binary Search is O(1) or constant space.
Top comments (0)