In this article, you will learn about the concepts of linear search and binary search algorithms, which one to choose, and how to implement them using the JavaScript language.

In computer science, the use of data structures and algorithms is extensive and important.

A data structure refers to the concept of how efficiently we can store and organize data.

On the other hand, the term “algorithms” refers to the concept of a collection of steps followed to solve a particular problem.

We can use data structures to organize our data and algorithms to process that data to solve a particular problem.

In this tutorial, we will implement the linear search and binary search algorithms using JavaScript.

**Prerequisite:**

There is no hard and fast rule to complete this tutorial. But if you want to complete it in the most effective way you need to keep some things in your mind.

- A configured computer with an internet connection.
- Basic knowledge of JavaScript for-loop.
- A text editor – You can choose any text editor on which you may write JavaScript code such as sublime text, nodepad++, etc. In this tutorial, we will use visual studio code.
- Installed NodeJS on your computer. We are using Node version
**v16.14.2.**You may use this version or higher. But it is recommended not to use the node version under 10.0.0 while completing this tutorial. - Nice to have little knowledge about JavaScript array if you don’t, no need to worry we will cover these later in this tutorial.

**The concept of array and JavaScript array**

In computer science, the array is considered a Data Structure where a similar type of multiple Data can be stored and used later when necessary.

Now, you can ask that, you can use variables for storing data then why use an array? The reason behind it is that we can only store a single piece of data at a time with variables.

But in a single array, we can store similar types of multiple data.

Let’s say you want to store `50`

students’ names in a classroom and if you want to perform this action by using variables then you need to use the 50 variables which will make your code Incomprehensible.

Now let’s imagine, what if the number of students is `2000`

or even more instead of 50? In such cases, it will be almost impossible to keep track of them if you use variables.

But you can perform this action very easily and cleanly by using the array and later on, you can access any data by using the array index.

In our introduction, we said that data structure is used to organize the data efficiently and you may already get an idea about it from the concept of the array section.

Because, if you notice carefully, you may be able to see that we are using an array to store and organize a large number of data.

We will use this basic data structure, we will implement the algorithms.

**Important: **The array index has started from `0(zero)`

and runs sequentially. Suppose, you have an array that consists three-element then the indexing for it will be `0, 1, 2`

.

**JavaScript Array**

The array in JavaScript is different from other programming languages and here it is considered as the Object.

We can store any type of data in the JavaScript array and it can be an Integer, String, Function, or Object. Here, we do not need to specify the array size before.

Let’s follow the below code example where you can see that in JavaScript the array is considered as the Object.

```
const arr = [10, 20, 30, 40, 50]
console.log(arr)
console.log(typeof(arr))
// Output:
//[ 10, 20, 30, 40, 50 ]
//'object'
```

Here, in JavaScript, we can check the data type by using the `typeof()`

method and we are trying to check the data type of our JavaScript array by using this and the result is in front of you.

To implement algorithms in a JavaScript array you need to know how to traverse it and let me assume that you already have known it.

Though let me quickly show you how you can traverse an array using for loop in JavaScript.

```
const arr = [10, 20, 30, 40, 50]
for(let i = 0; i<arr.length; i++){
console.log(arr[i])
}
/*
Output:
10
20
30
40
50
*/
```

Here, in the output, you can see that we have traversed each element of our array data using the `for-loop`

.

Now we are ready to jump into our algorithm section and in the next section, we are going to implement the linear search algorithm in JavaScript.

**Linear Search implementation**

The linear search algorithm is the most common search algorithm.

Here, each data is sequentially checked, and if the data exists then it returns the index number of that data from the array otherwise returns -1.

In other words, data has been found if it exists and data is not found if it does not exist.

It is also known as the `brute-force algorithm`

let’s see a basic example of a linear search algorithm using a JavaScript array in the below section:

```
function linearSearch(arr, target){
for(let i = 0; i < arr.length; i++){
if(arr[i] === target){
return console.log('Value found at index',i)
}
}
return console.log('Value not found')
}
linearSearch([10, 22, 44, 65, 34, 89], 44)
// Output: Value found at index 2
```

Here is the basic implementation of the linear search algorithm in JavaScript.

Here in our program, you can see that we have taken a function named `linearSearch()`

This function expects two parameters, the first one is the `array`

and the second one is the `target`

the value that the user wants to find.

Finally, you can see that, when we pass an array and a target value, this algorithm checks sequentially each data and compare it with the target value. when it finds the data simply returns it.

**Linear Search time complexity analysis with Graph**

While calculating the time complexity of an algorithm we have to always consider the worst-case scenario.

Because we don’t know what will be input the user will give.

In the best-case scenario, the time complexity of the linear search algorithm is `O(1)`

, and in the worst-case scenario `O(n)`

.

That means if we have an array of 100 core data then in the best-case scenario it will take only one search to find out the data and in the worst-case scenario, it will take 100 core times to search to find out the data.

Let’s see the graph of linear search algorithms’ time complexity:

Here, you can see that the graph line increases higher when the volume of data increases.

That means we can say that it is not applicable while working with a large amount of data.

Then what algorithm should we use to handle a large amount of data? In the next section, we are going to explore that.

**Binary Search implementation**

Binary search is a kind of algorithm that is used to find out a particular array element position from a sorted array.

It is also known as half-interval search, logarithmic search, or binary chop.

The main base of this algorithm is `divide and conquer`

.

This algorithm is very efficient to deal with a large amount of data. Let’s see the implementation of this algorithm using JavaScript:

```
var binarySearch = function(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){
right = mid - 1
}else{
left = mid + 1
}
}
return -1
};
console.log(binarySearch([10,20,33,44,54,65,77,79,80,100],77))
// Output: 6
```

Here, this algorithm first divides the array and then checks if the value is on the left side or right side. Let’s say it’s on the right side, then it simply removes the left side element.

Then again divide the rest of the array size and so on.

By following this approach, one can find out a particular value from the array within a few amount of searches.

**Important:** You always should remember that the binary search algorithm is only applicable to the sorted array.

**Binary Search time complexity analysis with Graph**

The binary search algorithm is very useful and plays an important role while finding particular data from the sorter array and the time complexity of this algorithm is `O(log n)`

That means the input’s size running time increases in the shape of the logarithm.

Let’s say, if the input size is 10 then it will take x times, if it is `100`

then it will take 2x times, if it is 1000 then it will take 3x, and so on so far. Let’s prove this concept mathematically in the below section:

Here, you can see that we have proved the time complexity of the binary search algorithm is O(log n) mathematically. Let’s see the time complexity graph of this algorithm in the below section:

Here, you can see that initially the graph line increases but the moment data increases the graph line is going to down. Now it’s time to take our knowledge one step ahead and see a binary search-related problem in the next section.

**Example or Order-agnostic Binary Search**

We have already known about what is the binary search algorithm and how it works.

Now, If you need to find a particular array element from a sorted array that is in ascending order then you can easily implement it or if the array elements are in descending order, you can also find it.

But what if, you don’t know the array order before then how can you implement the binary search algorithm to find a particular data?

Let’s say the array can be sorted in ascending order or in descending order.

How can you implement the binary search algorithm here? We will see the solution in the below section. But before doing so, I want you to think about it and try to find out the solution and then match your solution with ours.

When our algorithm is able to find out the data from the both ascending and descending sorted array then it is called the `Order-Agnostic Binary Search`

Let’s see the below code example of this algorithm:

```
function orderAgnosticBinarySearch(arr, target){
let left = 0
let right = arr.length -1
let mid = Math.floor((left+right)/2)
let isAsending
if(arr[left] < arr[right]){
isAsending = true
}else{
isAsending = false
}
while(left <= right){
if(arr[mid] === target){
return mid
}
if(isAsending){
if(arr[mid] > target){
right = mid - 1
}else{
left = mid + 1
}
}else{
if(arr[mid] < target){
right = mid - 1
}else{
left = mid + 1
}
}
mid = Math.floor((left+right)/2)
}
return -1
}
console.log(orderAgnosticBinarySearch([1,2,3,4,5,77,88,99,100],88))
console.log(orderAgnosticBinarySearch([100,99,88,77,5,4,3,2,1],88))
// Output:
// 6
// 2
```

Here, you can see that we have searched for the same data but from the ascending and descending order sorted array. We are getting the output 6 for the ascending sorted array and 2 for the descending sorted array.

That means our program is working perfectly and in the programming language, this concept is known as the Order Agnostic Binary Search.

**Conclusion**

The concept of the Data structures and Algorithm is very large. From this tutorial, you have known only about binary search and linear search, how they work, and their time complexity. You have also got an idea about array and JavaScript array.

This tutorial will help you to grow your interest in the Data structure and algorithms world. The mastery of these algorithms will not come overnight.

You need to practice more and more and try to experiment with these. Try to understand the concept of these algorithms from this tutorial and try to solve problems on different online Judges.

Because to become a good programmer you need to be a good problem solver. If you complete this tutorial properly, let me give you a challenge. Try to explore the concept of `floor`

and `ceiling`

and then try to solve this problem with a binary search.

Let’s say you have an array of [1, 5, 6, 8, 11, 15].

Now from this array, you need to find out the floor of 9 which is 8, or the ceiling of 9 which is 11.

That means if the array element is exist then return the index number of that element from the array and if it does not exist then return either the floor or the ceil index number from the array.

This is all about these two algorithms. Take this tutorial as the reference for your learning and try to solve this problem and make sure you did not copy or search the result of this problem.

If you solve this problem you can notice me in the comment section and if you have any confusion then you can also describe it in the comment section.