Binary Search

Gabriel Maciel — Sat, 25 Feb 2023 03:10:53 +0000

What is Binary Search?

A binary search is an algorithm used to find the position of a specific value in a sorted array. The algorithm repeatedly divides the search interval in half until the value is found or the search interval becomes empty.

Example of a Binary Search function in Javascript:

function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;

  while (left <= right) {
    let mid = Math.floor((left + right) / 2);

    if (arr[mid] === target) {
      return mid;
    } else if (arr[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }

  return -1;
}

The binarySearch function takes two arguments: the array to be searched (arr) and the target value to be found (target). It initializes two pointers, left and right, to the beginning and end of the array, respectively.

The function then enters a while loop that continues as long as left is less than or equal to right. In each iteration, the function calculates the midpoint index (mid) of the search interval using the formula (left + right) / 2. It then compares the value at the midpoint with the target value.

If the midpoint value is equal to the target value, the function returns the midpoint index. If the midpoint value is less than the target value, the function updates left to mid + 1, effectively discarding the left half of the search interval. If the midpoint value is greater than the target value, the function updates right to mid - 1, effectively discarding the right half of the search interval.

If the function completes the while loop without finding the target value, it returns -1 to indicate that the value was not found in the array.

Here's an example of how to use the binarySearch function:

const arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
const target = 7;

const index = binarySearch(arr, target);
console.log(index); // Output: 6

When to use Binary Search?

Binary search is a very efficient algorithm for searching in a sorted array or list. It has a time complexity of O(log n), which is much faster than linear search (which has a time complexity of O(n)).

Binary search is particularly useful when searching through very large datasets or when search performance is critical. It is commonly used in applications such as search engines, databases, and scientific computing.

Binary search is most effective when:

The data is sorted: Binary search requires the data to be sorted in order for the algorithm to work correctly. If the data is not sorted, the algorithm may not find the correct answer.
The data is static or nearly static: If the data is constantly changing, binary search may not be the best algorithm to use. Each time the data changes, the sorting process must be repeated, which can be very time-consuming.
The data size is large: Binary search is most effective when the data set is large. If the data set is small, the overhead of sorting the data and implementing the algorithm may not be worth the performance benefits.

In summary, binary search is a powerful algorithm that can provide significant performance improvements in the right situations. If you need to search through a large dataset that is static or nearly static and sorted, binary search is a great option to consider.

Top 10 Array Methods in JavaScript

Gabriel Maciel — Wed, 22 Feb 2023 19:13:04 +0000

JavaScript arrays are one of the most commonly used data structures in the language. Arrays are a powerful and flexible tool that can be used to store and manipulate data in a variety of ways. Here are the top 10 array methods in JavaScript along with examples of how they can be used:

1. push()

The push() method adds one or more elements to the end of an array and returns the new length of the array.

Example:

const array1 = [1, 2, 3];
array1.push(4);
console.log(array1); // [1, 2, 3, 4]

2. pop()

The pop() method removes the last element from an array and returns that element.

Example:

const array1 = [1, 2, 3];
const lastElement = array1.pop();
console.log(lastElement); // 3
console.log(array1); // [1, 2]

3. shift()

The shift() method removes the first element from an array and returns that element.

Example:

const array1 = [1, 2, 3];
const firstElement = array1.shift();
console.log(firstElement); // 1
console.log(array1); // [2, 3]

4. unshift()

The unshift() method adds one or more elements to the beginning of an array and returns the new length of the array.

Example:

const array1 = [1, 2, 3];
array1.unshift(4, 5);
console.log(array1); // [4, 5, 1, 2, 3]

5. slice()

The slice() method returns a shallow copy of a portion of an array into a new array object.

Example:

const array1 = [1, 2, 3, 4, 5];
const array2 = array1.slice(1, 3);
console.log(array2); // [2, 3]

6. splice()

The splice() method changes the contents of an array by removing or replacing existing elements and/or adding new elements.

Example:

const array1 = [1, 2, 3, 4, 5];
array1.splice(2, 1, 6);
console.log(array1); // [1, 2, 6, 4, 5]

7. concat()

The concat() method is used to merge two or more arrays into a new array.

Example:

const array1 = [1, 2, 3];
const array2 = [4, 5, 6];
const newArray = array1.concat(array2);
console.log(newArray); // [1, 2, 3, 4, 5, 6]

8. filter()

The filter() method creates a new array with all elements that pass the test implemented by the provided function.

Example:

const array1 = [1, 2, 3, 4, 5];
const filteredArray = array1.filter(num => num > 2);
console.log(filteredArray); // [3, 4, 5]

9. map()

The map() method creates a new array populated with the results of calling a provided function on every element in the calling array.

Example:

const array1 = [1, 2, 3];
const mappedArray = array1.map(num => num * 2);
console.log(mappedArray); // [2, 4, 6]

10. reduce()

The reduce() method applies a function against an accumulator and each element in the array to reduce it to a single value.

Example:

const array1 = [1, 2, 3, 4, 5];
const reducedValue = array1.reduce((accumulator, currentValue) => accumulator + currentValue);
console.log(reducedValue); // 15

These are the top 10 array methods in JavaScript. There are many other methods available that can help you manipulate arrays in different ways. Understanding these methods will help you write more efficient and concise code.

DEV Community: Gabriel Maciel

Binary Search

What is Binary Search?

When to use Binary Search?

Top 10 Array Methods in JavaScript

1. push()

2. pop()

3. shift()

4. unshift()

5. slice()

6. splice()

7. concat()

8. filter()

9. map()

10. reduce()