Difference Between Linear Search And Binary Search (+Code Example)

0 min read

In the world of algorithms, searching plays a pivotal role in problem-solving. Whether you're finding a specific item in a shopping list or looking up a contact in your phonebook, the concept of searching is everywhere. Two popular search algorithms in programming are linear search and binary search.

Linear search takes a straightforward approach, checking each element one by one. On the other hand, binary search divides and conquers the dataset to locate the target efficiently. In this article, we will discuss the difference between linear search and binary search, what makes them unique, and understand their applications.

What Is Linear Search?

Linear search is one of the simplest search algorithms. It scans each element in a list one at a time, starting from the beginning until it finds the target value or reaches the end of the list.

For example, say you're searching for a specific book on a messy bookshelf. Since the books aren't arranged in any particular order, you have no choice but to check them one by one until you find the book you need.

How Linear Search Works

1. Start with the first element of the list.
2. Compare it with the target value.
3. If it matches, return its position (or the value itself).
4. If not, move to the next element and repeat until the target is found or the list ends.

What Is Binary Search?

Binary search is a highly efficient search algorithm that works on sorted datasets. It follows the divide-and-conquer strategy, repeatedly dividing the search space in half until the target value is found or the search space is empty.

Imagine you're looking for a specific word in a dictionary. Instead of starting from the first page and checking every word, you'd flip to the alphabet section, compare the word there with your target, and decide whether to search in the first half or the second half of the dictionary. This significantly reduces the number of pages you need to check.

How Binary Search Works

1. Start by identifying the middle element of the sorted dataset.
2. Compare the middle element with the target value:
• If it matches, return its position.
• If the target is smaller, focus on the left half of the dataset.
• If the target is larger, focus on the right half.
3. Repeat the process on the reduced dataset until the target is found or the search space becomes empty.

Note: Binary search only works on sorted datasets. If the data is unsorted, you'll need to sort it first before applying binary search.

Difference Between Linear Search And Binary Search

Listed in the table below are the differences between linear search and binary search to provide a clear distinction between the two, emphasizing their strengths, limitations, and use cases.

Check out this amazing course to become the best version of the Python programmer you can be.

Example Of Linear Search Vs. Binary Search

We already have had a snapshot view of the difference between linear search and binary search. Now, let’s look at how both linear and binary search apply to the same array data structure in C++ programming language for comparison. This combined example will help illustrate how each algorithm performs with the same data.

Dataset:

int arr[] = {10, 20, 30, 40, 50, 60, 70, 80, 90};
int target = 40;

Linear Search Code Example:

            #include 
using namespace std;

int linearSearch(int arr[], int size, int target) {
for (int i = 0; i < size; i++) {
if (arr[i] == target) {
return i;  // Return index if found
}
}
return -1;  // Return -1 if not found
}

int main() {

int arr[] = {10, 20, 30, 40, 50, 60, 70, 80, 90};
int target = 40;

int size = sizeof(arr) / sizeof(arr[0]);
int result = linearSearch(arr, size, target);

if (result != -1) {
cout << "Linear Search: Element found at index " << result << endl;
} else {
cout << "Linear Search: Element not found" << endl;
}


return 0;
}
          

I2luY2x1ZGUgPGlvc3RyZWFtPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKaW50IGxpbmVhclNlYXJjaChpbnQgYXJyW10sIGludCBzaXplLCBpbnQgdGFyZ2V0KSB7CmZvciAoaW50IGkgPSAwOyBpIDwgc2l6ZTsgaSsrKSB7CmlmIChhcnJbaV0gPT0gdGFyZ2V0KSB7CnJldHVybiBpO8KgIC8vIFJldHVybiBpbmRleCBpZiBmb3VuZAp9Cn0KcmV0dXJuIC0xO8KgIC8vIFJldHVybiAtMSBpZiBub3QgZm91bmQKfQoKaW50IG1haW4oKSB7CgppbnQgYXJyW10gPSB7MTAsIDIwLCAzMCwgNDAsIDUwLCA2MCwgNzAsIDgwLCA5MH07CmludCB0YXJnZXQgPSA0MDsKCmludCBzaXplID0gc2l6ZW9mKGFycikgLyBzaXplb2YoYXJyWzBdKTsKaW50IHJlc3VsdCA9IGxpbmVhclNlYXJjaChhcnIsIHNpemUsIHRhcmdldCk7CgppZiAocmVzdWx0ICE9IC0xKSB7CmNvdXQgPDwgIkxpbmVhciBTZWFyY2g6IEVsZW1lbnQgZm91bmQgYXQgaW5kZXggIiA8PCByZXN1bHQgPDwgZW5kbDsKfSBlbHNlIHsKY291dCA8PCAiTGluZWFyIFNlYXJjaDogRWxlbWVudCBub3QgZm91bmQiIDw8IGVuZGw7Cn0KCgpyZXR1cm4gMDsKfQ==

Output:

Linear Search: Element found at index 3

Code Explanation:

In the C++ program example:

• We define a function linearSearch() which takes an array data structure, its size, and the target value as inputs.
• Inside, we use a for loop to iterate through the array from the start (index 0) to the end.
• For each element, we use an if-statement to checks if the current element equals the target value. 
• If a match is found, it returns the index of the element.
• If a match is not found the loop moves to the next element.
• If the loop completes without finding the target, the function returns -1, indicating the target is not in the array.
• In the main() function, we declare an array, arr with the dataset, and an integer variable, target with the value 40.
• Then, we use the sizeof() operator to find the size of the array.
• We then call the function linearSearch() passing the array, its size and the target as arguments.
• The function returns the index position of the target number, which we then print to the console after validating in an if-else statement.
• Finally, the main() function completes with the return 0 statement.

Binary Search Code Example:

            #include 
using namespace std;

int binarySearch(int arr[], int size, int target) {
int low = 0, high = size - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == target) {
return mid; // Return index if found
}
if (arr[mid] < target) {
low = mid + 1; // Search the right half
} else {
high = mid - 1; // Search the left half
}
}
return -1; // Return -1 if not found
}

int main() {

int arr[] = {10, 20, 30, 40, 50, 60, 70, 80, 90};
int target = 40;
int size = sizeof(arr) / sizeof(arr[0]);

int result = binarySearch(arr, size, target);
if (result != -1) {
cout << "Binary Search: Element found at index " << result << endl;
} else {
cout << "Binary Search: Element not found" << endl;
}

return 0;
}
          

I2luY2x1ZGUgPGlvc3RyZWFtPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKaW50IGJpbmFyeVNlYXJjaChpbnQgYXJyW10sIGludCBzaXplLCBpbnQgdGFyZ2V0KSB7CmludCBsb3cgPSAwLCBoaWdoID0gc2l6ZSAtIDE7CndoaWxlIChsb3cgPD0gaGlnaCkgewppbnQgbWlkID0gbG93ICsgKGhpZ2ggLSBsb3cpIC8gMjsKaWYgKGFyclttaWRdID09IHRhcmdldCkgewpyZXR1cm4gbWlkOyAvLyBSZXR1cm4gaW5kZXggaWYgZm91bmQKfQppZiAoYXJyW21pZF0gPCB0YXJnZXQpIHsKbG93ID0gbWlkICsgMTsgLy8gU2VhcmNoIHRoZSByaWdodCBoYWxmCn0gZWxzZSB7CmhpZ2ggPSBtaWQgLSAxOyAvLyBTZWFyY2ggdGhlIGxlZnQgaGFsZgp9Cn0KcmV0dXJuIC0xOyAvLyBSZXR1cm4gLTEgaWYgbm90IGZvdW5kCn0KCmludCBtYWluKCkgewoKaW50IGFycltdID0gezEwLCAyMCwgMzAsIDQwLCA1MCwgNjAsIDcwLCA4MCwgOTB9OwppbnQgdGFyZ2V0ID0gNDA7CmludCBzaXplID0gc2l6ZW9mKGFycikgLyBzaXplb2YoYXJyWzBdKTsKCmludCByZXN1bHQgPSBiaW5hcnlTZWFyY2goYXJyLCBzaXplLCB0YXJnZXQpOwppZiAocmVzdWx0ICE9IC0xKSB7CmNvdXQgPDwgIkJpbmFyeSBTZWFyY2g6IEVsZW1lbnQgZm91bmQgYXQgaW5kZXggIiA8PCByZXN1bHQgPDwgZW5kbDsKfSBlbHNlIHsKY291dCA8PCAiQmluYXJ5IFNlYXJjaDogRWxlbWVudCBub3QgZm91bmQiIDw8IGVuZGw7Cn0KCnJldHVybiAwOwp9

Output:

Binary Search: Element found at index 3

Code Explanation:

In the example C++ code:

• We define a function binarySearch() which takes an array data structure, its size, and the target value as inputs. 
• Inside, we initialize two variables, low and high, which represent the range of the array we are searching within. 
• Initially, low is set to the first index (0) and high to the last index (size - 1). 
• We then use a while loop to continue searching as long as low is less than or equal to high. In each iteration of the loop, we calculate the middle index mid using the formula low + (high - low) / 2. 
• This helps avoid overflow when low and high are large. We then compare the element at arr[mid] to the target value:
• If arr[mid] equals the target, we return the index mid.
• If arr[mid] is less than the target, we narrow our search to the right half of the array by setting low to mid + 1.
• If arr[mid] is greater than the target, we search the left half of the array by setting high to mid - 1.
• If the loop ends without finding the target, the function returns -1, indicating the target is not present in the array.
• In the main() function, we declare an array arr with the dataset and an integer variable target with the value 40.

• We then call the binarySearch() function, passing the array, its size, and the target value.
• If the function returns an index (indicating the target was found), we print it to the console. Otherwise, we display a message stating that the element was not found.

Linear Search Vs. Binary Search– Code Explanation

Linear Search: This algorithm will check the elements one by one, starting with the first element in the list. 

• In the example, the target 40 is found at index 3 after checking the elements in the linear array data structure: 10, 20, 30.
• It iterates over the array and checks each element until it finds the target.
• This is a simple approach but can be slow for large datasets, as it requires checking each element until the target is found.
• It works even on unsorted data, making it versatile but inefficient for large datasets (time complexity O(n)).

Binary Search: The binary search function repeatedly divides the search space in half, comparing the middle element with the target.

• In the example, it begins by comparing the target 40 with the middle element of the array (50). 
• Since 40 is smaller than 50, we update high to the middle index minus one and search the left half of the array. 
• In the next iteration, we compare 40 with 30 and shift the low pointer to mid + 1, moving to the right side of the array. Eventually, we find the target at index 3.
• It only works on sorted arrays, and it drastically reduces the search space in each step (time complexity O(log n)).
• Notice how quickly the binary search narrows down the dataset, even though both methods are searching for the same target value.

Difference Between Linear Search and Binary Search Explained

While both linear search and binary search are techniques for finding a target element in an array, they differ significantly in terms of efficiency, methodology, and application. Let’s break down the key differences:

Search Strategy | Linear Search Vs. Binary Search

1. Linear Search: This method scans the array from the first to the last element, checking each element sequentially to see if it matches the target. There is no optimization or divide-and-conquer strategy; it just goes one element at a time.
2. Binary Search: In contrast, binary search follows a divide-and-conquer strategy. It works by repeatedly dividing the search space in half. With each comparison, it eliminates half of the elements from the search space, narrowing down the potential location of the target.

Data Structure Requirements | Linear Search Vs. Binary Search

1. Linear Search: Linear search is flexible. It can work on both sorted and unsorted data. The search is conducted by checking every element, regardless of the array’s order.
2. Binary Search: Binary search requires that the array be sorted. The algorithm assumes that the array is in a specific order (either ascending or descending), and it uses that order to eliminate portions of the array that do not contain the target.

Time Complexity | Linear Search Vs. Binary Search

1. Linear Search: The time complexity of linear search is O(n), where n is the number of elements in the array. This is because, in the worst case, the algorithm has to check every element once.
2. Binary Search: Binary search has a time complexity of O(log n), where n is the number of elements in the array. Each step halves the size of the search space, making it much faster than linear search, especially for large datasets.

Best-Case Scenario | Linear Search Vs. Binary Search

1. Linear Search: The best-case scenario for linear search occurs when the target element is the first element of the array. In this case, the search will terminate after just one comparison.
2. Binary Search: The best-case scenario for binary search happens when the middle element of the array is the target. In this case, the algorithm immediately finds the target with a single comparison.

Efficiency in Large Datasets | Linear Search Vs. Binary Search

1. Linear Search: Linear search becomes slower as the size of the dataset increases because it has to check every element in sequence. It is not efficient for large arrays.
2. Binary Search: Binary search is far more efficient for large datasets. Since it reduces the search space exponentially, it can find the target much faster, even in very large arrays.

Memory Usage | Linear Search Vs. Binary Search

1. Linear Search: Linear search operates in constant space (O(1)) as it doesn’t require any extra storage. It simply uses a loop and a few variables to perform the search.
2. Binary Search: Similarly, binary search also operates in constant space (O(1)) for iterative implementations. However, if implemented recursively, it may use additional memory on the call stack (O(log n)).

Flexibility | Linear Search Vs. Binary Search

1. Linear Search: Linear search is more versatile because it doesn’t require sorted data. It can be used in a variety of scenarios where the data may be unordered.
2. Binary Search: Binary search is less flexible because it requires sorted data. If the data is unsorted, you must sort it first, which can add to the time complexity.

While linear search is useful for smaller or unsorted datasets, binary search excels in large, sorted arrays. Choosing the right search algorithm depends on the data you’re working with and the size of the array.

Linear Search Vs. Binary Search | Advantages and Disadvantages

Both linear and binary search algorithms come with their unique strengths and limitations. While linear search is simple and versatile, it becomes inefficient as the dataset grows. On the other hand, binary search is much faster for large, sorted datasets but requires pre-sorting and a bit more complexity in implementation. Let’s break down the advantages and disadvantages of each algorithm to better understand where each shines and where they fall short.

Conclusion

In this article, we've explored the fundamental differences between Linear Search and Binary Search, two essential algorithms for searching through arrays. 

• Linear Search is straightforward and works well for small or unsorted datasets, while Binary Search offers significant performance benefits for large, sorted datasets by quickly narrowing down the search space.
• Each algorithm has its place, depending on the problem at hand. For unsorted data, linear search is your go-to solution, whereas binary search is optimal for scenarios requiring fast lookups in sorted data. 
• Understanding when and where to apply each search method is crucial for optimizing performance in real-world applications.

By comparing these two algorithms through code examples and in-depth analysis, we hope you now have a clear understanding of the differences between linear search and binary search. And are familiar with their respective advantages, disadvantages, and ideal use cases.

Ready to test your knowledge of DSA? Dive deeper into actual problem statements and elevate your coding game with hands-on practice!

Frequently Asked Questions

Q1. What is the time complexity of Linear Search?

The time complexity of linear search is O(n), as it checks each element in the array until it finds the target or reaches the end of the list.

Q2. Can Binary Search be used on unsorted data?

No, binary search can only be applied to sorted data. If the data is unsorted, it needs to be sorted first, which can take additional time.

Q3. Which search algorithm is faster for small datasets?

For small datasets, linear search might be faster since it’s simpler and doesn’t require the data to be sorted. However, for larger datasets, binary search is generally more efficient.

Q4. How does Binary Search work in a sorted array?

Binary search repeatedly divides the array into halves, comparing the middle element with the target. Based on the comparison, it eliminates half of the remaining search space until it finds the target or determines it's not in the array.

Q5. Can Linear Search be used in a sorted array?

Yes, linear search can be used in a sorted array, but binary search is a more efficient choice for such data since it reduces the search space significantly with each step.

Knowing the difference between linear search and binary search will help you decide when to choose the simplicity of linear search or the speed of binary search. Here are a few more topics you must explore:

1. Advantages And Disadvantages Of Array Explained (+Applications)
2. Python List sort() | All Use Cases Explained (+Code Examples)
3. One Dimensional Array In Java | Operations & More (+Code Examples)
4. Learn How To Sort An Array In Java (With Detailed Code Examples)
5. Hello World Program In C | How-To Write, Compile & Run (+Examples)