Mastering Top 10 JS Algorithms
Mastering Top 10 JS Algorithms
Interview Questions and Anwsers
Reverse String
**Algorithm Name**: Reverse String
* **Questions**:
The task is to reverse a given string. The input is a string and the output should also be a string, but in reversed order.
* **Time Complexity**:
- Brute Force: N/A
in this case since there is not much of a way to brute force this problem.
- Optimized:
O(n), you must iterate over each character of the original string once.
* **Space Complexity**:
- Brute Force: N/A
- Optimized:
O(n), you're creating an array with as many elements as there are characters in the string.
* **Approaches**:
- Optimized:
- First, .split('') is used to convert the string into an array where each character of the string is a separate element.
- Then .reverse() is used to reverse the order of the elements in the array.
- Finally, .join('') is used to convert the array back into a string.
- Brute Force: N/A
* **Explanation**:
This function splits the input string into an array of characters, reverses the order of the array, and then joins the elements of the array back into a string. The result is the input string in reversed order.
* **Sample Code**: javascript
- Optimized: *ES5---
//Unit Test
console.log(reverseString('facebook'));
let rs =reverseString('hello');
console.log(rs);
- Optimized:*ES6---
* **Questions**:
The task is to reverse a given string. The input is a string and the output should also be a string, but in reversed order.
* **Time Complexity**:
- Brute Force: N/A
in this case since there is not much of a way to brute force this problem.
- Optimized:
O(n), you must iterate over each character of the original string once.
* **Space Complexity**:
- Brute Force: N/A
- Optimized:
O(n), you're creating an array with as many elements as there are characters in the string.
* **Approaches**:
- Optimized:
- First, .split('') is used to convert the string into an array where each character of the string is a separate element.
- Then .reverse() is used to reverse the order of the elements in the array.
- Finally, .join('') is used to convert the array back into a string.
- Brute Force: N/A
* **Explanation**:
This function splits the input string into an array of characters, reverses the order of the array, and then joins the elements of the array back into a string. The result is the input string in reversed order.
* **Sample Code**: javascript
- Optimized: *ES5---
function reverseString(str){
return str.split('').reverse().join('');
}
//Unit Testconsole.log(reverseString('facebook'));
let rs =reverseString('hello');
console.log(rs);
- Optimized:*ES6---
const reverseString = str => [...str].reverse().join('');
// Test case
console.log(reverseString('facebook'));
Palindrome Check
**Algorithm Name**: Palindrome Check
* **Questions**:
Does case matter in our palindrome check?
Do we keep or remove white spaces, digits or special characters when checking for the palindrome property?
How do we handle null or undefined input?
* **Time Complexity**:
- Single Solution: O(n) where n is the length of the string.
* **Space Complexity**:
- Single Solution: O(n) where n is the length of the string. Javascript's string split method will create a new array that contains every character in the string as individual elements.
* **Approaches**:
- **Summary of Steps**
- Split the string into an array of individual characters.
- Reverse the order of the array of characters.
- Join the reversed array of characters back into a string.
- Compare the reversed string to the original string.
* **Explanation**:
A palindrome is a word, phrase or sequence that reads the same backwards as forwards. Therefore, to determine if the string is a palindrome, we need to reverse the string and check it against the original string. If they are the same, we can say that the string is a palindrome otherwise it is not.
* **Sample Code**:javascript
function isPalindrome(str) {
* **Example**:
- Input: 'racecar'
- Output: true
Here is an example demo with the racecar input:
//Unit Test
console.log(isPalindrome("racecar")); // Outputs: true
* **Questions**:
Does case matter in our palindrome check?
Do we keep or remove white spaces, digits or special characters when checking for the palindrome property?
How do we handle null or undefined input?
* **Time Complexity**:
- Single Solution: O(n) where n is the length of the string.
* **Space Complexity**:
- Single Solution: O(n) where n is the length of the string. Javascript's string split method will create a new array that contains every character in the string as individual elements.
* **Approaches**:
- **Summary of Steps**
- Split the string into an array of individual characters.
- Reverse the order of the array of characters.
- Join the reversed array of characters back into a string.
- Compare the reversed string to the original string.
* **Explanation**:
A palindrome is a word, phrase or sequence that reads the same backwards as forwards. Therefore, to determine if the string is a palindrome, we need to reverse the string and check it against the original string. If they are the same, we can say that the string is a palindrome otherwise it is not.
* **Sample Code**:javascript
function isPalindrome(str) {
// Split the string into individual characters
const charArray = str.split('');
// Reverse the order of charArray
const reversedArray = charArray.reverse();
// Join the reversed array back into a string
const reversed = reversedArray.join('');
// Return whether the reversed string is equal to the original string
return str === reversed;
}
* **Example**:- Input: 'racecar'
- Output: true
Here is an example demo with the racecar input:
//Unit Test
console.log(isPalindrome("racecar")); // Outputs: true
FizzBuzz Algorithm
**Algorithm Name**: FizzBuzz Algorithm
* **Question**: What is Fizz Buzz algorithm?
* **Time Complexity**:
- Optimized: O(n)
* **Space Complexity**:
- Optimized: O(1)
* **Approaches**:
- Optimized: Loop from 1 to n and print 'Fizz' if the number is divisible by 3, 'Buzz' if the number is divisible by 5, 'FizzBuzz' if the number is divisible by both 3 and 5, else print the number.
* **Explanation**:
The FizzBuzz algorithm is a common programming task, used in interviews to weed out non-programmers during hiring process. It is asked to write a program that prints the numbers from 1 to n. But for multiples of three, print "Fizz" instead of the number, and for multiples of five, print "Buzz". For numbers which are multiples of both three and five, print "FizzBuzz".
* **Sample Code**:javascript
const fizzBuzz = (n) => {
* **Example**:
//Unit Test
console.log(fizzBuzz(15));
- Input: `fizzBuzz(15)`
- Output: The program prints the following:
1
2
Fizz
4
Buzz
Fizz
7
8
Fizz
Buzz
11
Fizz
13
14
FizzBuzz
This is because 'Fizz' replaces multiples of 3, 'Buzz' replaces multiples of 5, and 'FizzBuzz' replaces multiples of
* **Question**: What is Fizz Buzz algorithm?
* **Time Complexity**:
- Optimized: O(n)
* **Space Complexity**:
- Optimized: O(1)
* **Approaches**:
- Optimized: Loop from 1 to n and print 'Fizz' if the number is divisible by 3, 'Buzz' if the number is divisible by 5, 'FizzBuzz' if the number is divisible by both 3 and 5, else print the number.
* **Explanation**:
The FizzBuzz algorithm is a common programming task, used in interviews to weed out non-programmers during hiring process. It is asked to write a program that prints the numbers from 1 to n. But for multiples of three, print "Fizz" instead of the number, and for multiples of five, print "Buzz". For numbers which are multiples of both three and five, print "FizzBuzz".
* **Sample Code**:javascript
const fizzBuzz = (n) => {
for(let i = 1; i <= n; i++) {
// Check if the number is a multiple of 3 and 5
if(i % 3 === 0 && i % 5 === 0) {
console.log('FizzBuzz');
}
// Check if the number is a multiple of 3
else if(i % 3 === 0) {
console.log('Fizz');
}
// Check if the number is a multiple of 5
else if(i % 5 === 0) {
console.log('Buzz');
}
else {
console.log(i);
}
}
}
* **Example**://Unit Test
console.log(fizzBuzz(15));
- Input: `fizzBuzz(15)`
- Output: The program prints the following:
1
2
Fizz
4
Buzz
Fizz
7
8
Fizz
Buzz
11
Fizz
13
14
FizzBuzz
This is because 'Fizz' replaces multiples of 3, 'Buzz' replaces multiples of 5, and 'FizzBuzz' replaces multiples of
Factorial Calculation
**Algorithm Name**: Factorial Calculation
* **Questions**:
What is the runtime limit for the function? Are negative inputs possible and how should they be handled?
* **Time Complexity**:
- Optimized: O(n)
* **Space Complexity**:
- Optimized: O(n) due to recursive stack space.
* **Approaches**:
- Optimized: Use a simple recursion to calculate the factorial of a number.
* **Explanation**:
A factorial of a number is the product of all positive integers up to that number.
A simple recursion can be used to calculate the factorial of a number. Zero factorial is defined as 1.
The base case for the recursion would be n = 0, where the function should return 1.
For any other positive number, the function will recursively call itself with decrementing n and multiply result with current n.
* **Sample Code**: javascript
function factorial(n){
//Javascript Unit Test
console.log(factorial(5)); // Outputs
- Input: factorial(5)
- Output: 120 (since 5*4*3*2*1 = 120)
Please make sure the input `n` is available before calling the function, otherwise, it'll lead to error as variable `n` is undefined currently in the provided code. Here is the correct code with a sample input and output.
console.log(factorial(5)); // Outputs
* **Questions**:
What is the runtime limit for the function? Are negative inputs possible and how should they be handled?
* **Time Complexity**:
- Optimized: O(n)
* **Space Complexity**:
- Optimized: O(n) due to recursive stack space.
* **Approaches**:
- Optimized: Use a simple recursion to calculate the factorial of a number.
* **Explanation**:
A factorial of a number is the product of all positive integers up to that number.
A simple recursion can be used to calculate the factorial of a number. Zero factorial is defined as 1.
The base case for the recursion would be n = 0, where the function should return 1.
For any other positive number, the function will recursively call itself with decrementing n and multiply result with current n.
* **Sample Code**: javascript
function factorial(n){
if(n === 0) return 1;
return n * factorial(n - 1);
}
//Javascript Unit Test console.log(factorial(5)); // Outputs
- Input: factorial(5)
- Output: 120 (since 5*4*3*2*1 = 120)
Please make sure the input `n` is available before calling the function, otherwise, it'll lead to error as variable `n` is undefined currently in the provided code. Here is the correct code with a sample input and output.
console.log(factorial(5)); // Outputs
Fibonacci Sequence
**Algorithm Name**: Fibonacci Sequence
* **Questions**:
Does the sequence start with 0 or 1? If asked to compute for a large number, how should I handle it?
* **Time Complexity**:
- Brute Force: O(2^n)
- Optimized: O(n)
* **Space Complexity**:
- Brute Force: O(n)
- Optimized: O(n)
* **Approaches**:
- Brute Force:
Recursively call fibonacci for n-1 and n-2 and add these together
- Optimized: Create a bottom-up approach using memoization to store fibonacci of each number up to n
* **Explanation**:
The Fibonacci sequence is a series of numbers where a number is found by adding up the two numbers before it.
The sequence starts 0, 1, 1, 2, 3, 5, 8, 13, 21, and so on. The brute force method recursively calculates each value, while the optimized solution keeps track of previously calculated values to avoid unnecessary recursion.
* **Sample Code**: Javascript
// Brute Force:
//Unit Test
* **Example**:
console.log(fibonacci(6)) // 8
console.log(fibonacciOptimized(6))
- Input: 6
- Output: 8
* **Questions**:
Does the sequence start with 0 or 1? If asked to compute for a large number, how should I handle it?
* **Time Complexity**:
- Brute Force: O(2^n)
- Optimized: O(n)
* **Space Complexity**:
- Brute Force: O(n)
- Optimized: O(n)
* **Approaches**:
- Brute Force:
Recursively call fibonacci for n-1 and n-2 and add these together
- Optimized: Create a bottom-up approach using memoization to store fibonacci of each number up to n
* **Explanation**:
The Fibonacci sequence is a series of numbers where a number is found by adding up the two numbers before it.
The sequence starts 0, 1, 1, 2, 3, 5, 8, 13, 21, and so on. The brute force method recursively calculates each value, while the optimized solution keeps track of previously calculated values to avoid unnecessary recursion.
* **Sample Code**: Javascript
// Brute Force:
fibonacci = (n) => {
if(n <= 1 ) {
return n;
}
return fibonacci(n-1)+ fibonacci(n-2);
}
// Optimized
fibonacciOptimized = (n) => {
let fib = [0, 1];
for (let i = 2; i <= n; i++) {
fib[i] = fib[i-1] + fib[i-2];
}
return fib[n];
}
//Unit Test* **Example**:
console.log(fibonacci(6)) // 8
console.log(fibonacciOptimized(6))
- Input: 6
- Output: 8
Anagram Validation
**Algorithm Name**: Anagram Validation
* **Questions**:
Are the strings case sensitive? Are the strings ASCII or Unicode strings? Are white spaces in the strings considered?
* **Time Complexity**:
- Both the "optimized" and "brute force" will give you the same result in this case: O(n log n) because a sort operation has a time complexity of O(n log n) where 'n' is the length of the string.
* **Space Complexity**:
- The space complexity is O(n) because we are creating extra string representations of the same length as the input strings.
* **Approaches**:
* **Optimized**:
In this case, the most efficient approach is to split the strings into individual characters, sort them and then join them back into strings. After this, you compare the two strings for equality.
* **Brute Force**:
You could create a histogram for each string (count the number of each character). Then compare the histograms to see if they have the same counts for each character. This can be much slower and more complex, but gives an alternative approach to consider.
* **Explanation**:
- For an anagram, when the characters of two strings are rearranged, they become the equal to each other.
Based on this property, we sort the strings alphabetically and then compare them for equality.
If the strings are equal after sorting, then they are anagrams of each other.
* **Sample Code**:JavaScript
const anagram = (s1, s2) => {
* **Example**:
- Input: "mary", "army"
- Output: true
**Unit Test
Input and Output**
console.log(anagram("mary", "army")); // true
console.log(anagram("listen", "silent")); // true
console.log(anagram("hello", "
//The End
* **Questions**:
Are the strings case sensitive? Are the strings ASCII or Unicode strings? Are white spaces in the strings considered?
* **Time Complexity**:
- Both the "optimized" and "brute force" will give you the same result in this case: O(n log n) because a sort operation has a time complexity of O(n log n) where 'n' is the length of the string.
* **Space Complexity**:
- The space complexity is O(n) because we are creating extra string representations of the same length as the input strings.
* **Approaches**:
* **Optimized**:
In this case, the most efficient approach is to split the strings into individual characters, sort them and then join them back into strings. After this, you compare the two strings for equality.
* **Brute Force**:
You could create a histogram for each string (count the number of each character). Then compare the histograms to see if they have the same counts for each character. This can be much slower and more complex, but gives an alternative approach to consider.
* **Explanation**:
- For an anagram, when the characters of two strings are rearranged, they become the equal to each other.
Based on this property, we sort the strings alphabetically and then compare them for equality.
If the strings are equal after sorting, then they are anagrams of each other.
* **Sample Code**:JavaScript
const anagram = (s1, s2) => {
// Split the string into an array of individual characters
// Sort the array in alphabetical order
// Join the sorted array back into a string
// Do this for both strings and then compare if the result is the same
return s1.split("").sort().join("") === s2.split("").sort().join("");
}
* **Example**:- Input: "mary", "army"
- Output: true
**Unit Test
Input and Output**
console.log(anagram("mary", "army")); // true
console.log(anagram("listen", "silent")); // true
console.log(anagram("hello", "
//The End
Array Maximum Visitable Webpages
**Algorithm Name**: Array Maximum Visitable Webpages
* **Questions**:
- N: Are there any constraints on the size of the input?
- L: Is the input sorted in any way?
- Are there any negative numbers?
* **Time Complexity**:
- Brute Force: O(n^2)
- Optimized: O(n log n)
* **Space Complexity**:
- Brute Force: O(n)
- Optimized: O(n)
* **Approaches**:
- Optimized: The optimized approach is to sort the array in ascending order on the basis of the time spent on each site, and then keep on adding it to a running sum until we run out of batteries, or we have visited all of the sites.
To do this, we make use of a priority queue(a max-heap data structure is maintained with the help of a PriorityQueue library of JAVA).
- Brute Force:
The brute force way of solving this question is to visit every possible combination of sites.
However, this is a very inefficient solution as it has a high time complexity of O(2^n).
* **Explanation**:
We need to begin visiting the sites such that we visit the sites with the least time required first. But, the site visit order doesn't matter.
Thus, we can ensure that we stick on to a policy of visiting the site requiring the least time first by making use of a Priority Queue which places the sites requiring lesser time at the first place always.
* **Sample Code**: language-javascript
getMaxVisitableWebpages = (N, L) => {
//Unit Test
Get the result with a sample input:
console.log(getMaxVisitableWebpages(10, [1, 2, 3, 4, 5, 6])); // Output: 4
console.log(getMaxVisitableWebpages(10, [1, 9, 5, 2])); // Output: 3
* **Example**:
- Input: N = 10, L = [1, 2, 3, 4, 5, 6]
- Output: 4
* **Questions**:
- N: Are there any constraints on the size of the input?
- L: Is the input sorted in any way?
- Are there any negative numbers?
* **Time Complexity**:
- Brute Force: O(n^2)
- Optimized: O(n log n)
* **Space Complexity**:
- Brute Force: O(n)
- Optimized: O(n)
* **Approaches**:
- Optimized: The optimized approach is to sort the array in ascending order on the basis of the time spent on each site, and then keep on adding it to a running sum until we run out of batteries, or we have visited all of the sites.
To do this, we make use of a priority queue(a max-heap data structure is maintained with the help of a PriorityQueue library of JAVA).
- Brute Force:
The brute force way of solving this question is to visit every possible combination of sites.
However, this is a very inefficient solution as it has a high time complexity of O(2^n).
* **Explanation**:
We need to begin visiting the sites such that we visit the sites with the least time required first. But, the site visit order doesn't matter.
Thus, we can ensure that we stick on to a policy of visiting the site requiring the least time first by making use of a Priority Queue which places the sites requiring lesser time at the first place always.
* **Sample Code**: language-javascript
getMaxVisitableWebpages = (N, L) => {
// We sort the array in ascending order
L.sort((a, b) => a - b);
let visitedWebpagesCount = 0, batteryInUse = 0;
// We iterate through the sorted array
for(let i = 0; i < L.length; i++) {
if(batteryInUse + L[i] <= N) {
// Consuming the webpage only when we have enough battery
batteryInUse += L[i];
visitedWebpagesCount++;
} else {
// Exiting the loop when the battery isn't enough
break;
}
}
return visitedWebpagesCount;
}
//Unit TestGet the result with a sample input:
console.log(getMaxVisitableWebpages(10, [1, 2, 3, 4, 5, 6])); // Output: 4
console.log(getMaxVisitableWebpages(10, [1, 9, 5, 2])); // Output: 3
* **Example**:
- Input: N = 10, L = [1, 2, 3, 4, 5, 6]
- Output: 4
Two Sum Problem
**Algorithm Name**: Two Sum Problem
* **Questions**:
- Does the input array contain only integers?
- Can the input array contain duplicate numbers?
- Does the pair needs to be sorted?
* **Time Complexity**:
- Brute Force: O(n^2)
- Optimized: O(n)
* **Space Complexity**:
- Brute Force: O(1)
- Optimized: O(n)
* **Approaches**:
- **Brute Force**:
- Brute Force: Iterate over the array multiple times comparing the current iteration with all the rest.
- Optimized: Use a hash table to store and look up the complement of the current element.
- **Optimized**:
Use a hash table (or an Object in JavaScript) to store the differences between the target and each element in the array.
For each element, if it's present as a key in the hash table, that means we've found a pair that adds up to the target.
This has a time complexity of O(n) because we're passing through the array only once.
* **Explanation**:
The optimized approach exploits the speed of lookups in a hash table (constant time, O(1)).
Instead of having to loop again through the array to find the matching pair, we immediately know if it exists thanks to the hash table.
* **Sample Code**:javascript
const twoSum = (nums, target) => {
// Test case
console.log(twoSum([2, 7, 11, 15], 9)); // Output:[ 0, 1 ]
- Input: nums = [2, 7, 11, 15], target = 9
**Test the function with an example**: console.log(twoSum([2,7,11,15], 9));
// Output: [0,1]
console.log(twoSum([3,2,4], 6));
// Output: [1,2]
console.log(twoSum([3,3], 6));
// Output: [ 0, 1 ]
* **Questions**:
- Does the input array contain only integers?
- Can the input array contain duplicate numbers?
- Does the pair needs to be sorted?
* **Time Complexity**:
- Brute Force: O(n^2)
- Optimized: O(n)
* **Space Complexity**:
- Brute Force: O(1)
- Optimized: O(n)
* **Approaches**:
- **Brute Force**:
- Brute Force: Iterate over the array multiple times comparing the current iteration with all the rest.
- Optimized: Use a hash table to store and look up the complement of the current element.
- **Optimized**:
Use a hash table (or an Object in JavaScript) to store the differences between the target and each element in the array.
For each element, if it's present as a key in the hash table, that means we've found a pair that adds up to the target.
This has a time complexity of O(n) because we're passing through the array only once.
* **Explanation**:
The optimized approach exploits the speed of lookups in a hash table (constant time, O(1)).
Instead of having to loop again through the array to find the matching pair, we immediately know if it exists thanks to the hash table.
* **Sample Code**:javascript
const twoSum = (nums, target) => {
const hash = {};
for (let i = 0; i < nums.length; i++) {
const complement = target - nums[i];
if (hash[nums[i]] !== undefined) {
return [hash[nums[i]], i];
}
hash[complement] = i;
}
return null;
};
// Test case
console.log(twoSum([2, 7, 11, 15], 9)); // Output:[ 0, 1 ]
- Input: nums = [2, 7, 11, 15], target = 9
**Test the function with an example**: console.log(twoSum([2,7,11,15], 9));
// Output: [0,1]
console.log(twoSum([3,2,4], 6));
// Output: [1,2]
console.log(twoSum([3,3], 6));
// Output: [ 0, 1 ]
Linked List Reversal
**Algorithm Name**: Linked List Reversal
* **Questions**:
- What is the structure of the linked list node?
- Should it modify the original list or return a new one?
* **Time Complexity**:
- Optimized: O(n)
* **Space Complexity**:
- Optimized: O(1)
* **Approaches**:
- Optimized: Here is a one-pass, O(n) time, O(1) space complexity iterative approach that scans the linked list, setting the `next` pointer of each node to the previous node.
* **Explanation**:
This algorithm walks over the linked list node by node.
In each step, it switches the 'next' of the node to be the previous node. By the end of the traversal, every 'next' pointer has been redirected backwards hence achieving the reversal of the linked list.
* **Sample Code**:javascript
function ListNode(val, next) {
* **Example**:
- Input: 1 -> 2 -> 3 -> 4 -> 5 -> NULL
- Output: 5 -> 4 -> 3 -> 2 -> 1 -> NULL
* **Questions**:
- What is the structure of the linked list node?
- Should it modify the original list or return a new one?
* **Time Complexity**:
- Optimized: O(n)
* **Space Complexity**:
- Optimized: O(1)
* **Approaches**:
- Optimized: Here is a one-pass, O(n) time, O(1) space complexity iterative approach that scans the linked list, setting the `next` pointer of each node to the previous node.
* **Explanation**:
This algorithm walks over the linked list node by node.
In each step, it switches the 'next' of the node to be the previous node. By the end of the traversal, every 'next' pointer has been redirected backwards hence achieving the reversal of the linked list.
* **Sample Code**:javascript
function ListNode(val, next) {
this.val = (val === undefined ? 0 : val)
this.next = (next === undefined ? null : next)
}
function reverseList(head) {
let prev = null;
let current = head;
while(current !== null){
// Store next node before we overwrite current.next
let nextTemp = current.next;
// Reverse current node's pointer
current.next = prev;
// Move pointers for next loop
prev = current;
current = nextTemp;
}
return prev;
}
// Unit Test
let node5 = new ListNode(5);
let node4 = new ListNode(4, node5);
let node3 = new ListNode(3, node4);
let node2 = new ListNode(2, node3);
let node1 = new ListNode(1, node2);
let reversedList = reverseList(node3);
while(reversedList !== null)
console.log(reversedList.val);
* **Example**:- Input: 1 -> 2 -> 3 -> 4 -> 5 -> NULL
- Output: 5 -> 4 -> 3 -> 2 -> 1 -> NULL
Binary Search
**Algorithm Name**:Binary Search
* **Questions**:
Is the input array sorted? Can the array contain duplicate values?
If yes, do we want to return the first occurrence, the last occurrence, or any occurrence of the target?
Note: For simplicity, the following implementation assumes that the array is sorted in ascending order and does not contain duplicate values.
* **Time Complexity**:
- Both Brute Force and Optimized: O(log n) where n is the size of the array.
The algorithm halves the size of the array in each iteration.
* **Space Complexity**:
- Both Brute Force and Optimized: O(1) as no extra space is required.
We are only using a few integer variables.
* **Approaches**: - Optimized: Initialize two pointers, left and right, to the start and end of the array respectively. Then, in a loop, calculate the middle element. If the target is equal to the middle element, return the middle index. If the target is less than the middle element, move the right pointer to middle - 1. If the target is greater than the middle element, move the left pointer to middle + 1. Continue this process until the left pointer is less than or equal to the right pointer or the target is found. * **Explanation**:
The Binary Search algorithm works by dividing the array into two halves and determining which half the target is likely to be in.
This allows us to discard half of the elements in each iteration.
This is why binary search is much faster than linear search in a sorted array.
* **Sample Code**:javascript
function binarySearch(arr, target) {
// Unit test
console.log(binarySearch([1, 2, 3, 4, 5, 6], 4)); // Output is 3
console.log(binarySearch([1, 2, 3, 4, 5, 6], 7)); // Output is -1 because 7 is not
- Input: arr = [1, 2, 3, 4, 5, 6], target = 4
- Output: 3 which is the index of target in the array
* **Questions**:
Is the input array sorted? Can the array contain duplicate values?
If yes, do we want to return the first occurrence, the last occurrence, or any occurrence of the target?
Note: For simplicity, the following implementation assumes that the array is sorted in ascending order and does not contain duplicate values.
* **Time Complexity**:
- Both Brute Force and Optimized: O(log n) where n is the size of the array.
The algorithm halves the size of the array in each iteration.
* **Space Complexity**:
- Both Brute Force and Optimized: O(1) as no extra space is required.
We are only using a few integer variables.
* **Approaches**: - Optimized: Initialize two pointers, left and right, to the start and end of the array respectively. Then, in a loop, calculate the middle element. If the target is equal to the middle element, return the middle index. If the target is less than the middle element, move the right pointer to middle - 1. If the target is greater than the middle element, move the left pointer to middle + 1. Continue this process until the left pointer is less than or equal to the right pointer or the target is found. * **Explanation**:
The Binary Search algorithm works by dividing the array into two halves and determining which half the target is likely to be in.
This allows us to discard half of the elements in each iteration.
This is why binary search is much faster than linear search in a sorted array.
* **Sample Code**:javascript
function binarySearch(arr, target) {
let left = 0; // Start pointer
let right = arr.length - 1; // End pointer
while (left <= right) {
let middle = Math.floor((left + right) / 2); // Calculate middle index
if (arr[middle] === target) { // If target is found at the middle index
return middle;
}
if (arr[middle] < target) {
// If target is greater than middle, move left pointer to middle + 1
left = middle + 1;
} else { // If target is less than middle, move right pointer to middle - 1
right = middle - 1;
}
}
return -1; // If target is not found, return -1
}
// Unit test console.log(binarySearch([1, 2, 3, 4, 5, 6], 4)); // Output is 3
console.log(binarySearch([1, 2, 3, 4, 5, 6], 7)); // Output is -1 because 7 is not
- Input: arr = [1, 2, 3, 4, 5, 6], target = 4
- Output: 3 which is the index of target in the array
Printer Friendly Version