Binary Search Algorithm | Javascript

Qayyum Shareef — Mon, 29 Nov 2021 16:40:55 +0000

The binary search algorithm works on the principle of divide and conquer. Before searching, the array has to be in the sorted form then the middle element in the array is checked. If the match is found the element index is returned.

If the middle element is less than the searching element then the search happens in the right sub-array otherwise, the search happens in left sub-array

Let's write some code

Consider an array of numbers, remember array indexing starts form zero '0'.

const numbers = [4, 10, 12, 26, 34, 39, 42, 57];

Now we have a function with arguments as sorted array and the number which we need to find.

function binarySearch(sortedArray, x) {
  let lowIndex = 0;
  let highIndex = sortedArray.length - 1;

  while (lowIndex <= highIndex) {
    let midIndex = lowIndex + Math.floor((highIndex - lowIndex) / 2);
    if (sortedArray[midIndex] === x) {
      return midIndex;
    } else if (sortedArray[midIndex] < x) {
      lowIndex = midIndex + 1;
    } else {
      highIndex = midIndex - 1;
    }
  }
  return -1;
}

binarySearch(numbers, 10); // returns 1
binarySearch(numbers, 34); // returns 4
binarySearch(numbers, 63); // since 63 is not there in numbers, returns -1

// Save the file and run it using Node.JS
// Open terminal and give command: node [filename].js

Math.floor() function rounds a number downward to its nearest integer.
for example: Math.floor(2.5) // returns 2

Time Complexity

The time complexity of Binary Search Algorithm is O(log n).

Best case scenario O(1), if the finding element is at centre.
Worst case scenario could be when the finding element is present at extremely left or right from centre and if it is not at all present in array.

Well, that's it folks. I hope you learned something share it with your friends. Follow me for more posts just like this and
if you have any questions let me know in the comment section.

Cheers!

Linear Search Algorithm | JavaScript

Qayyum Shareef — Thu, 19 Aug 2021 19:39:40 +0000

In Linear Search or Sequential Search, every element in the array is checked, and if the match is found then the element index is returned otherwise, the search continues till the last element.

Lets write some code

Always remember that array indexing starts from Zero - '0'

const numbers = [2, 4, 67, 8, 44, 6, 12];

Now, lets write a function to apply linear search algorithm to above array.

function linearSearch(array, num) {
  for (let i = 0; i < array.length; i++) {
    if (array[i] === num) {
      return i;
    }
  }
  return -1;
}

linearSearch(numbers, 8); // returns index 4
linearSearch(numbers, 28); // since 28 is not there, returns -1 

// Save the file and run it using Node.JS
// Open terminal and give command: node [filename].js

Time Complexity

The time complexity of Linear Search Algorithm is O(n).

let's improve the worst case scenario.

If the search element found at last. O(n) -> O(1)
If the search element not found. O(n) -> O(n/2)

function betterLinearSearch(array, element) {
  let length = array.length;
  let left = 0;
  let right = length - 1;

  let position = -1;

  while (left <= right) {
    if (array[left] == element) {
      position = left;
      console.log(`${element} is present at index ${position}. attempt ${left + 1}`);
      break;
    }

    if (array[right] == element) {
      position = right;
      console.log(`${element} is present at index ${position}. - attempt ${length - right}`);
      break;
    }
    left++;
    right--;
  }

  if (position == -1) {
    console.log(`${element} not found. attempt ${left}`);
  }
}

betterLinearSearch(numbers, 8); 
// Try with a last element and check the attempts in log
betterLinearSearch(numbers, 12); 
betterLinearSearch(numbers, 28);

// Save the file and run it using Node.JS
// Open terminal and give command: node [filename].js

In every iteration, first and last element from the array is being checked.
After every iteration the left index needed to be increased and right index needed to be decreased.
When position value remains -1 it means the element is not present in array.

Well, that's it folks. I hope you learned something share it with your friends. Follow me for more posts just like this and let me know your thoughts in the comment section.

Cheers!

DEV Community: Qayyum Shareef

Binary Search Algorithm | Javascript

Let's write some code

Time Complexity

Linear Search Algorithm | JavaScript

Lets write some code

Time Complexity