Binary Search Concept

Do you want to understand binary search? Read this article, I have discussed binary search problems in JavaScript.

Binary Search Concept

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 problems

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 Algorithm

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;
}

See the Pen Binary Search on Sorted Array Algorithm by Rupesh Tiwari (@roopkt) on CodePen.

Binary Search Problems in JavaScript

While I was watching his lecture I converted all of the problem solutions in JavaScript.

Find if given number is a SQUARE

Question

function isSquare(x) {}
describe('IsSquare', () => {
  it('should work correctly #1', () => {
    expect(isSquare(16)).toBeTruthy();
  });
  it('should work correctly #2', () => {
    expect(isSquare(6570204424081)).toBeFalsy();
  });
});

Answer

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;
}

See the Pen by Rupesh Tiwari (@roopkt) on CodePen.

Find Square Root of given Number

Question

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);
  });
});

Answer

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;
    }
  }
}

See the Pen by Rupesh Tiwari (@roopkt) on CodePen.

Find first value greater than equals to given number

Question

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);
  });
});

Answer

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;
}

See the Pen Find First Value greater than given number by Rupesh Tiwari (@roopkt) on CodePen.

Find Minimum in Circularly Sorted Array

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.

Question

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);
  });
});

Answer

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 array

Question

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);
  });
});

Answer

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;
}

See the Pen Find Maximum in increasing decreasing array by Rupesh Tiwari (@roopkt) on CodePen.

All Binary Search Basic problems

Here is the link to see all binary search basic questions

References

• Errichto Binary Search YouTube video
• Errichto Github repo

---

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 💻

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 Rupesh and 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