Algorithms: Linear Search and Binary Search

There are some simple algorithms that introduce basic concepts of logic and data structure, while others aim for greater complexity.

Search algorithms are useful for locating information in volumes of data, such as finding a contact in a phone book or a file on a computer.

In this sense, this article aims to present an introduction to the concepts involving Linear Search and Binary Search algorithms.

1. Linear Search

• Scan through a list sequentially to find an element
• An example would be to search for a specific number in an array

The Linear Search Algorithm, in a narrative statement, means having an array of integers and a value that will be the reference for the search, called target, which will be the input parameters. In this sense, there is a function that receives these values, and with that, first it goes through each position of this array up to the maximum size of existing positions, using primarily a for for this, and then, with an if, it is conditioned the check for: whether each position has a value equal to the target. If the value is found, the function returns the index of that position, or returns -1, representing cases not found.

An example using JavaScript would be:

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

Therefore, this algorithm aims to return the position, or index, where the element is located, or even, it simply locates the first corresponding element, without the need to continue after finding it. This behavior occurs due to the instructions of the algorithm, which, when its condition is satisfied, executes the return with the element index, and after that it exits the loop, ending the function.

This algorithm can be useful in scenarios where there are small or unordered lists. Each element can need to be traversed, and there is no extra memory usage.

2. Binary Search

• Scroll through an ordered list to find an element
• An example would be searching for a specific number in an array

The Binary Search Algorithm is a more efficient form of algorithm for finding a given value in a sorted array. This works by repeatedly dividing the search range in half, which makes it significantly faster than linear search for large datasets. Binary search has O(log n) complexity, while linear search is O(n).

As an example in JavaScript, we have:

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

The logic consists of starting with two pointers, one at the beginning (low) and the other at the end (high) of the array. Thus, the middle index is calculated const middle = Math.floor((low high) / 2). With this, the middle element is compared with the target at each step: if the middle element is equal to the target, the index is returned. However, if the middle element is smaller than the target, or middle < target, implies discarding the smallest numbers, placing the beginning as low = middle 1. If the middle element, in turn, is greater than the target middle > target, numbers greater than the target are discarded, adjusting the final index to high = middle - 1. This process is repeated until the target is found or when the range becomes invalid, in the case low > high.

Binary search can be efficient when finding ordered data, such as in an alphabetical dictionary or a set of ordered dates. They tend to be faster and more efficient, as the problem can be divided into smaller subproblems in each iteration.

Therefore, it is understood that linear search is simple and works on small lists. Binary search is much more efficient, but requires ordered data.

Understanding how different algorithms work and their contexts of use is an important step towards building efficient computational solutions. Try implementing and analyzing these methods, and discover how these strategies can be adapted to solve real-world challenges. =)

The above is the detailed content of Algorithms: Linear Search and Binary Search. For more information, please follow other related articles on the PHP Chinese website!