Binary Search
Published: 2023-11-06 19:05:34

Searching refers to iterating over the data structure's elements to retrieve some data. When searching in an array, there are two main techniques depending on whether the array is sorted.
With regards to Linear and Binary searching, Linear searches are especially flexible because they can be used with both sorted and unsorted data while Binary searches are specifically used with sorted data.

Linear Search
A linear search works by going through each element of the array one index after another sequentially. The following code example is an implementation of a linear search that iterates through the entire array of numbers to find out whether an item exists within the array.


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

// Example usage:
const numbers = [4, 2, 7, 1, 9, 3];
const target = 7;
const result = linearSearch(numbers, target)
```

Binary Tree
Generally, when beginners in programming attempt to perform a loop to find something in an array, they resort to linear search, an algorithm with little efficiency that analyzes each index of the array in search of the desired element. To put it simply, it's like reading an entire dictionary in search of just a small word.

Unlike linear search, binary search has the "spirit" of divide and conquer. It repeatedly divides a data collection in two, which allows vast data portions not to be analyzed.

```ts
function pesquisaBinariaPrimos(array, targe) {
  let left = 0;
  let right = array.length - 1;

  while (left <= right) {
    const half = Math.floor((letf + right) / 2);

    if (array[half] === targe) {
      return half; 
    } else if (array[half] < targe) {
      left = half + 1;
    } else {
      right = half - 1;
    }
  }

  return -1; 
}
```
   
 Those with a basic knowledge of algorithms and JavaScript can already understand the steps and processes of the code.

 
![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/hmia9l0j18uzquql9bcs.jpeg)


With a sorted dataset, we can take advantage of the order to make a search more efficient than going element by element.

Let's say you're looking for the word "Telescope" in the dictionary. You don't leaf through the words "A" and "B," page by page until you get to the desired page because you know that "T" is near the end of the alphabet.

You can open it near the end and see the words "R." Maybe then you jump ahead and reach the words with "V." You then backtrack a bit to find the words "T."

At each point, you could look forward or backward based on the order of the alphabet. We can use this intuition for an algorithm called binary search.

Binary search requires a sorted dataset. We then follow the following steps:

1. Check the middle value of the dataset.
2. If this value matches our target, we can return the index.
3. If the middle value is less than our target, start at step 1 using the right half of the list.
4. If the middle value is greater than our target, start at step 1 using the left half of the list.
5. Finally, we either run out of values in the list or find the target value.