Binary Search Concept
Do you want to understand binary search? Read this article, I have discussed binary search problems in JavaScript.
Binary Search ConceptPermalink
Please watch this YouTube video from Errichto. This is the best binary search video I have ever seen. Next solve all the problems as he is going in his lecture.
Binary search can be done on a given sorted array and it is is used to perform:
- Search a number
- Search a number with given conditions
- Find real values like square, square root etc.
Thumb of rule for Binary Search problemsPermalink
Divide your array in set of TRUE and FALSE values then find the First occurrence of TRUE or the last occurrence of TRUE. Binary Search Array should be partially false and partially true. We need to find the boundary between them.
Binary Search AlgorithmPermalink
function binarySearch(array, data) {
let low = 0;
let high = array.length - 1;
while (low <= high) {
let mid = low + Math.floor((high - low) / 2);
if (data === array[mid]) return mid;
else if (data < array[mid]) high = mid - 1;
else low = mid + 1;
}
return -1;
}
Binary Search Problems in JavaScriptPermalink
While I was watching his lecture I converted all of the problem solutions in JavaScript.
Find if given number is a SQUAREPermalink
QuestionPermalink
function isSquare(x) {}
describe('IsSquare', () => {
it('should work correctly #1', () => {
expect(isSquare(16)).toBeTruthy();
});
it('should work correctly #2', () => {
expect(isSquare(6570204424081)).toBeFalsy();
});
});
AnswerPermalink
function isSquare(x) {
// For Array the maximum length is 2GB-1 (2^32-1)
if (x >= Math.pow(2, 32)) return false;
const array = Array.from(Array(Math.floor(x / 2)).keys());
let low = 0;
let high = array.length - 1;
let mid;
let square;
while (low <= high) {
mid = low + Math.floor((high - low) / 2);
square = Math.pow(array[mid], 2);
if (x === square) return true;
else if (x < square) high = mid - 1;
else low = mid + 1;
}
return false;
}
Find Square Root of given NumberPermalink
QuestionPermalink
function sqrt(x) {}
describe('Find Square Root of x', () => {
it('should work correctly #1', () => {
expect(sqrt(4)).toBe(2);
});
it('should work correctly #2', () => {
expect(sqrt(36)).toBe(6);
});
});
AnswerPermalink
function sqrt(x) {
var array = Array.from(Array(x).keys());
let low = 0;
let high = array.length - 1;
while (low <= high) {
let mid = low + Math.floor((high - low) / 2);
let square = array[mid] * array[mid];
if (square === x) {
return mid;
} else if (square > x) {
high = mid - 1;
} else {
low = mid + 1;
}
}
}
Find first value greater than equals to given numberPermalink
QuestionPermalink
function findFirstValue(array, data) {}
describe('Find First Value >= x in sorted array', () => {
it('should work correctly #1', () => {
expect(findFirstValue([2, 3, 5, 6, 8, 10, 12], 4)).toBe(5);
});
});
AnswerPermalink
function findFirstValue(array, data) {
let low = 0;
let high = array.length - 1;
let mid;
let result = -1;
while (low <= high) {
mid = low + Math.floor((high - low) / 2);
if (array[mid] >= data) {
result = array[mid];
high = mid - 1; // since I need first occurrence so keep searching in the left sorted half of the array.
} else low = mid + 1;
}
return result;
}
Find Minimum in Circularly Sorted ArrayPermalink
This is also the pivot number in a circularly sorted array. Once you find the pivot element then it’s index value can also tell you how many times the array is shifted / rotated. The index of pivot element will give you count or rotation as well.
QuestionPermalink
function findMinInCircularlySortedArray(array) {}
describe('Find Min in Circularly Sorted Array', () => {
it('should work correctly #1', () => {
expect(findMinInCircularlySortedArray([11, 12, 15, 18, 2, 5, 6, 8])).toBe(
2
);
});
it('should work correctly #2', () => {
expect(findMinInCircularlySortedArray([6, 7, 9, 15, 19, 2, 3])).toBe(2);
});
});
AnswerPermalink
function findMinInCircularlySortedArray(array) {
let low = 0;
let length = array.length;
let high = length - 1;
let mid;
let result = -1;
while (low <= high) {
mid = low + Math.floor((high - low) / 2);
if (array[mid] <= array[length - 1]) {
result = array[mid];
high = mid - 1;
} else {
low = mid + 1;
}
}
return result;
}
Find Maximum number in increasing decreasing arrayPermalink
QuestionPermalink
function findMaximumInIncreasingDecreasingArray(array) {}
describe('find Maximum In Increasing and Decreasing Array', () => {
it('should work correctly #1', () => {
expect(
findMaximumInIncreasingDecreasingArray([
2,
3,
4,
6,
9,
12,
11,
8,
6,
4,
1,
])
).toBe(12);
});
});
AnswerPermalink
function findMaximumInIncreasingDecreasingArray(array) {
let low = 0;
let high = array.length - 1;
let mid;
let answer = -1;
while (low <= high) {
mid = low + Math.floor((high - low) / 2);
if (array[mid] >= array[mid - 1] || mid === 0) {
answer = array[mid];
low = mid + 1;
} else {
high = mid - 1;
}
}
return answer;
}
All Binary Search Basic problemsPermalink
Here is the link to see all binary search basic questions
ReferencesPermalink
Thanks for reading my article till end. I hope you learned something special today. If you enjoyed this article then please share to your friends and if you have suggestions or thoughts to share with me then please write in the comment box.
Become full stack developer 💻Permalink
I teach at Fullstack Master. If you want to become Software Developer and grow your carrier as new Software Engineer or Lead Developer/Architect. Consider subscribing to our full stack development training programs. You will learn Angular, RxJS, JavaScript, System Architecture and much more with lots of hands on coding. We have All-Access Monthly membership plans and you will get unlimited access to all of our video courses, slides, download source code & Monthly video calls.
- Please subscribe to All-Access Membership PRO plan to access current and future angular, node.js and related courses.
- Please subscribe to All-Access Membership ELITE plan to get everything from PRO plan. Additionally, you will get access to a monthly live Q&A video call with
Rupeshand you can ask doubts/questions and get more help, tips and tricks.
Your bright future is awaiting for you so visit today FullstackMaster and allow me to help you to board on your dream software company as a new Software Developer, Architect or Lead Engineer role.
💖 Say 👋 to me!
Rupesh Tiwari
Founder of Fullstack Master
Email: rupesh.tiwari.info@gmail.com
Website: www.rupeshtiwari.com | www.fullstackmaster.net
