Data structures & algorithms (Beginner to Intermediate)

Free guided path13 chapters99+ problems

Earn badges and level up

Introduction

If you are planning to study DSA in deep, you should know that searching and sorting algorithms are neccessary. In searching, we have two algorithms. The two algorithms are

These two search algorithms are very efficient in searching elements. They are used to search for a particular element in an array.

Now let's discuss linear and binary search with its implementation. We will also discuss its properties and the difference between linear search and binary search.

What is Linear Search?

Linear search is the basic searching algorithm. It is a sequential searching technique in which we begin at one end of the list and continue checking each element until the required element appears. Let's see a diagram to understand the linear search clearly.

In the above diagram, we have to search for 4. Firstly we will compare 15 with 4. The value is not the same, so we will move forward. Again we will compare 50 with 4. The value is not the same, so we will again move forward. We will proceed in this manner. In the end, when we will compare 4 with 4, the value will be the same. The element can be found in this way.

Now you must have gotten the idea of linear search. Let us now see the implementation of linear search in different languages

Get the tech career you deserve, faster!

Connect with our expert counsellors to understand how to hack your way to success

User rating 4.7/5

1:1 doubt support

95% placement record

Akash Pal

Senior Software Engineer

326% Hike After Job Bootcamp

Himanshu Gusain

Programmer Analyst

32 LPA After Job Bootcamp

After Job Bootcamp

Implementation of Linear Search

Following are the implementation of linear search in various programming languages.

Implementation in C++

C++

C++

#include<iostream> using namespace std; int main() { int a[10],i,pos,n,item,op,flag; cout<<"enter the size of array: "; cin>>n; cout<<"enter elements of the array: "; for(i=0;i<n;i++) { cin>>a[i]; } cout<<"enter the element to search: "; cin>>item; flag=0; for(i=0;i<n;i++) { if(a[i]==item) { flag=1; break; } } if(flag==0) { cout<<"item not found"; } else { cout<<"item found at location: "<<i; }

}

Output

enter the size of array: 5
enter elements of the array: 12 23 43 54 42
enter the element to search: 23
item found at location: 1

Explanation

In the output shown above, firstly, we have to enter the size and elements of the array. Then we have to search for element 23 in the array. As you can see, the element is at the first index of the array. So, the value returned here is index 1.

Implementation in Python

Python

Python

def search_item(arr, n, item): flag = 0 for i in range(n): if arr[i] == item: flag = 1 print("Item found at location:", i) break if flag == 0: print("Item not found")

if __name__ == "__main__": a = [0] * 10 n = int(input("Enter the size of array: ")) print("Enter elements of the array: ") for i in range(n): a[i] = int(input()) item = int(input("Enter the element to search: ")) search_item(a, n, item)

Output

Enter the size of array: 5
Enter elements of the array:
34
56
21
11
78
Enter the element to search: 78
Item found at location: 4

Explanation

In the output shown above, firstly, we have to enter the size and elements of the array. Then we have to search for element 78 in the array. As you can see, the element is at the fourth index of the array. So, the value returned here is index 4.

In the next section of the blog, we will see some properties of the linear search.

Properties of Linear Search

Some properties of the linear search are the following:

Linear search is the simplest search algorithm.

It is a sequential search algorithm.

It begins at one end of the list and continues checking each element until the required element appears.

It works on both sorted and unsorted arrays.

Linear search is effective on small datasets.

The best case time complexity of the linear search is O(1), and the average case time complexity is O(n).

What is Binary Search?

To know the difference between linear search and binary search, you should have the idea of binary search too. You can use the binary search algorithm, a divide and conquer technique, to look for and locate elements in a sorted array. Because it skips half of the array each time the search iteration occurs, the algorithm is quick when looking for elements.

As a result, the algorithm searches across the portion of the array that contains the element it is looking for rather than the entire array. This repeats until the element is located. Let us see a diagram to get a better grasp on binary search.

In the above diagram, we have to find element 70 using binary search. Firstly we are calculating the low and high index of the array. According to the low and high indices, we are finding the mid. At first, the low index is at 0, the high index is at 4, and the mid index is at 2. It is clear that the element at mid is smaller than the target element. So we will move to the right subarray and again calculate the low, high, and mid index. We will move recursively like this and will find the target element.

Now we will see the implementation of binary search in different languages.

Implementation of Binary Search

Following are the implementation of binary search in various programming languages.

Implementation in C++

C++

C++

#include<iostream> using namespace std; int main() { int a[10],i,pos,n,item,op,flag; cout<<"enter the size of array: "; cin>>n; cout<<"**for binary search array must be sorted**"<<endl; cout<<"enter elements of the array: "; for(i=0;i<n;i++) { cin>>a[i]; } int beg,mid,end; cout<<"enter element to search: "; cin>>item; beg=0; end=n-1; flag=0; mid=(beg+end)/2; while(a[mid] != item && beg<=end) { if(item>a[mid]) { beg = mid+1; } else { end = mid-1; } mid=(beg+end)/2; if(a[mid]==item) {

flag=1; break; } } if(flag==1) { cout<<"element found at index: "<<mid; } else if(flag==0) { cout<<"element not found"; } }

Output

enter the size of array: 5
**for binary search array must be sorted**
enter elements of the array: 12 34 56 78 90
enter element to search: 34
element found at index: 1

Explanation

In the output shown above, firstly, we have to enter the size and elements of the array. It is clearly written that binary search only works on sorted arrays. We have to search for element 34 in the array. As you can see, the element is at the first index of the array. So, the value returned here is index 1.

Implementation in Python

Python

Python

def binary_search(arr, item): n = len(arr) beg = 0 end = n - 1 while beg <= end: mid = (beg + end) // 2 if arr[mid] == item: return mid elif item > arr[mid]: beg = mid + 1 else: end = mid - 1 return -1

if __name__ == "__main__": a = [0] * 10 n = int(input("Enter the size of array: ")) print("**For binary search, array must be sorted**") print("Enter elements of the array: ") for i in range(n): a[i] = int(input()) item = int(input("Enter element to search: ")) index = binary_search(a, item) if index != -1: print("Element found at index:", index) else: print("Element not found")

Output

Enter the size of array: 5
**For binary search, array must be sorted**
Enter elements of the array:
34
45
56
67
78
Enter element to search: 56
Element found at index: 2

Explanation

In the output shown above, firstly, we have to enter the size and elements of the array. It is clearly written that binary search only works on sorted arrays. We have to search for element 56 in the array. As you can see, the element is at the second index of the array. So, the value returned here is index 2.

Now in the next section of the blog, we will see some properties of the binary search.

Properties of Binary Search

Some properties of binary search are the following:

The binary search follows the divide-and-conquer approach.

It is also known as a logarithmic search.

For the binary search to work, the array should always be sorted.

It constantly divides the array according to the mid element until it finds the target element.

Binary search work efficiently on large datasets.

The time complexity of the binary search is O(log n).

Now let us move to the next section of the blog to know the difference between linear search and binary search.

Difference Between Linear Search and Binary Search

In this section of the blog, we will discuss the key difference between linear search and binary search. We are already aware of linear search and binary search in detail. Now it's time to discuss the difference between linear search and binary search.

Parameters

Linear Search

Binary Search

Complexity

Linear search is the simplest searching algorithm.

Binary search follows the divide and conquer approach to find the element.

Definition

It begins at one end of the list and continues checking each element until the required element appears.

The algorithm searches across the portion of the array that contains the element it is looking for rather than the entire array. This repeats until the element is located

Also known

It is also known as sequential searching.

It is also known as a logarithmic search or half-interval search.

Efficiency

It is efficient on small datasets.

It is efficient on large datasets.

Requirement

It works on both sorted and unsorted arrays.

It works on sorted arrays only.

Time complexity

The time complexity of the linear search is O(n).

The time complexity of the binary search is O(log n).

Best case

The best case is when we find the element at the first position of the array.

The best case is when the target element is the middle element of the array.

What drawbacks does binary search have over linear search?

Binary search is prone to mistakes. There could be overlapping inaccuracies when defining the next interval's border. The caching is bad. Binary search's recursive approach utilizes stack space. When computing indices in large arrays, overflows could occur.

How are linear and binary searches used?

Binary search can only be performed on one-dimensional arrays, but linear search can be used on both single and multiple arrays. When big data sets are taken into account, linear search is less effective than binary search.

Which is faster, linear or binary search?

Except for small arrays, binary search is faster than linear search. However, sorting the array is required before doing a binary search. Binary search can be done more effectively using specialized data structures created for quick searching, such as hash tables.

What are three examples of linear functions in real life?

Three examples of linear functions in real life include:

Cost of renting a car, where the total cost depends on the number of days rented.

Distance traveled by a car at a constant speed over time.

Salary increase based on years of experience, with a fixed rate of increment.

Conclusion

As we have reached the end of this blog, let us see what we have discussed so far. In this blog, we have seen the basics of linear search. We saw its implementation in C++ and Java and some of its properties. Then we discussed the binary search along with its implementation in C++ and Java and its properties. In the end, we saw the difference between linear search and binary search.

For more content, refer to our articles on similar topics:

But if you have just started your learning process and looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc., you must have a look at the following links interview experiencesandinterview bundle.