Assume that item is in an array in random order and we have to find an item. Then the only way to search for a target item is, to begin with, the first position and compare it to the target. If the item is at the same, we will return the position of the current item. Otherwise, we will move to the next position. If we arrive at the last position of an array and still can not find the target, we return -1. This is called the Linear search or Sequential search.
Below is the code syntax for the linear search.
C++
// Linear Search in C++
#include <iostream>
usingnamespacestd;
intsearch(intarray[], intn, intx)
{
// Going through array sequencially
for(inti = 0; i < n; i++)
if(array[i] == x)
returni;
return-1;
}
C
// Linear Search in C
#include <stdio.h>
intsearch(intarray[], intn, intx)
{
// Going through array sequencially
for(inti = 0; i < n; i++)
if(array[i] == x)
returni;
return-1;
}
Java
/*package whatever //do not write package name here */
importjava.io.*;
classMain {
publicstaticintliner(intarr[], intx)
{
for(inti = 0; i < arr.length; i++) {
if(arr[i] == x)
returni;
}
return-1;
}
}
Python
# Linear Search in Python
deflinearSearch(array, n, x):
fori inrange(0, n):
if(array[i] ==x):
returni
return-1
C#
// Linear Search in c#
usingSystem;
usingSystem.Collections.Generic;
classGFG
{
publicstaticintsearch(int[] array, intn, intx)
{
// Going through array sequencially
for(inti = 0; i < n; i++)
if(array[i] == x)
returni;
return-1;
}
}
// This code is contributed by adityapatil12.
Javascript
<script>
// Linear Search in C++
functionsearch(array, n, x)
{
// Going through array sequencially
for(let i = 0; i < n; i++){
if(array[i] == x){
returni;
}
}
return-1;
}
// The coee is contributed by Gautam goel.
</script>
BINARY SEARCH
In a binary search, however, cut down your search to half as soon as you find the middle of a sorted list. The middle element is looked at to check if it is greater than or less than the value to be searched. Accordingly, a search is done to either half of the given list
// Repeat until the pointers low and high meet each
// other
while(low <= high) {
intmid = low + (high - low) / 2;
if(array[mid] == x)
returnmid;
if(array[mid] < x)
low = mid + 1;
else
high = mid - 1;
}
return-1;
}
Java
/*package whatever //do not write package name here */
classGFG {
publicstaticintbinary(int[] arr, intx)
{
intstart = 0;
intend = arr.length - 1;
while(start <= end) {
intmid = (start + end) / 2;
if(x == arr[mid]) {
returnmid;
}
elseif(x > arr[mid]) {
start = mid + 1;
}
else{
end = mid - 1;
}
}
return-1;
}
}
Python
defbinarySearch(array, x, low, high):
# Repeat until the pointers low and high meet each other
whilelow <=high:
mid =low +(high -low)//2
ifarray[mid] ==x:
returnmid
elifarray[mid] < x:
low =mid +1
else:
high =mid -1
return-1
C#
// Linear Search in c#
usingSystem;
usingSystem.Collections.Generic;
classGFG
{
publicstaticintbinary(int[] arr, intx)
{
intstart = 0;
intend = arr.Length - 1;
while(start <= end) {
intmid = (start + end) / 2;
if(x == arr[mid]) {
returnmid;
}
elseif(x > arr[mid]) {
start = mid + 1;
}
else{
end = mid - 1;
}
}
return-1;
}
}
// This code is contributed by aditya942003patil
Javascript
<script>
functionbinarySearch(array, x, low, high)
{
// Repeat until the pointers low and high meet each
// other
while(low <= high) {
int mid = low + (high - low) / 2;
if(array[mid] == x){
returnmid;
}
if(array[mid] < x){
low = mid + 1;
}
else{
high = mid - 1;
}
}
return-1;
}
// The code is contributed by gautam goel.
</script>
Important Differences
Linear Search
Binary Search
In linear search input data need not to be in sorted.
In binary search input data need to be in sorted order.
It is also called sequential search.
It is also called half-interval search.
The time complexity of linear search O(n).
The time complexity of binary search O(log n).
Multidimensional array can be used.
Only single dimensional array is used.
Linear search performs equality comparisons
Binary search performs ordering comparisons
It is less complex.
It is more complex.
It is very slow process.
It is very fast process.
Let us look at an example to compare the two:
Linear Search to find the element “J” in a given sorted list from A-X
Binary Search to find the element “J” in a given sorted list from A-X
LINEAR SEARCHING EXAMPLE:
C++
#include <iostream>
usingnamespacestd;
intsearch(intarray[], intn, intx)
{
// Going through array sequencially
for(inti = 0; i < n; i++)
if(array[i] == x)
returni;
return-1;
}
intmain()
{
intarray[] = { 12, 114, 0, 4, 9 };
intx = 4;
intn = sizeof(array) / sizeof(array[0]);
intresult = search(array, n, x);
(result == -1)
? cout << "Element not found"
: cout << "Element found at index: "<< result;
}
C
#include <stdio.h>
intsearch(intarray[], intn, intx)
{
// Going through array sequencially
for(inti = 0; i < n; i++)
if(array[i] == x)
returni;
return-1;
}
intmain()
{
intarray[] = { 12, 114, 0, 4, 9 };
intx = 4;
intn = sizeof(array) / sizeof(array[0]);
intresult = search(array, n, x);
(result == -1)
? printf("Element not found")
: printf("Element found at index: %d", result);
}
Java
/*package whatever //do not write package name here */
importjava.io.*;
classGFG {
publicstaticintliner(intarr[], intx)
{
for(inti = 0; i < arr.length; i++) {
if(arr[i] == x)
returni;
}
return-1;
}
publicstaticvoidmain(String[] args)
{
intarr[] = { 12, 114, 0, 4, 9};
intsearch = liner(
arr,
4); // Here we are searching for 10 element in
// the array which is not present in the
// array so, it will print -1
System.out.println(search);
}
}
Python
deflinearSearch(array, n, x):
fori inrange(0, n):
if(array[i] ==x):
returni
return-1
array =[24, 41, 31, 11, 9]
x =11
n =len(array)
result =linearSearch(array, n, x)
if(result ==-1):
print("Element not found")
else:
print("Element is Present at Index: ", result)
C#
// C# program to implement above approach
usingSystem;
usingSystem.Collections.Generic;
classGFG
{
publicstaticintliner(int[] arr, intx)
{
for(inti = 0; i < arr.Length; i++) {
if(arr[i] == x)
returni;
}
return-1;
}
// Driver Code
publicstaticvoidMain(string[] args){
int[] arr = { 12, 114, 0, 4, 9 };
intsearch = liner(arr, 4); // Here we are searching for 10 element in
// the array which is not present in the
// array so, it will print -1
Console.Write(search);
}
}
//this code is contributed by aditya942003patil
Javascript
functionsearch(array, n, x)
{
// Going through array sequencially
for(let i = 0; i < n; i++)
if(array[i] == x)
returni;
return-1;
}
array = [12, 114, 0, 4, 9 ];
x = 4;
n = array.length;
result = search(array, n, x);
if(result == -1){
console.log("Element not found");
}
else{
console.log("Elementn found at index: ", result);
}
// The code is contributed by Nidhi goel
Output
Element found at index: 3
Time Complexity: O(n), where n is the size of the input array. The worst-case scenario is when the target element is not present in the array, and the function has to go through the entire array to figure that out. Auxiliary Space: O(1), the function uses only a constant amount of extra space to store variables. The amount of extra space used does not depend on the size of the input array.
// Repeat until the pointers low and high meet each
// other
while(low <= high) {
intmid = low + (high - low) / 2;
if(array[mid] == x)
returnmid;
if(array[mid] < x)
low = mid + 1;
else
high = mid - 1;
}
return-1;
}
intmain( )
{
intarray[] = { 2, 4, 5, 17, 14, 7, 11, 22 };
intn = sizeof(array) / sizeof(array[0]);
intx = 22;
intresult = binarySearch(array, x, 0, n - 1);
if(result == -1)
printf("Not found");
else
printf(" %d", result);
return0;
}
Java
/*package whatever //do not write package name here */
publicclassGFG {
publicstaticintbinary(intarr[], intx)
{
intstart = 0;
intend = arr.length - 1;
while(start <= end) {
intmid = (start + end) / 2;
if(x == arr[mid]) {
returnmid;
}
elseif(x > arr[mid]) {
start = mid + 1;
}
else{
end = mid - 1;
}
}
return-1;
}
publicstaticvoidmain(String[] args)
{
intarr[] = { 2, 4, 5, 17, 14, 7, 11, 22};
intsearch = binary(arr, 22);
System.out.println(search);
}
}
Python
defbinarySearch(array, x, low, high):
whilelow <=high:
mid =low +(high -low)//2
ifarray[mid] ==x:
returnmid
elifarray[mid] < x:
low =mid +1
else:
high =mid -1
return-1
array =[2, 4, 5, 17, 14, 7, 11, 22]
x =22
result =binarySearch(array, x, 0, len(array)-1)
ifresult !=-1:
print(str(result))
else:
print("Not found")
C#
usingSystem;
usingSystem.Collections.Generic;
classGFG
{
publicstaticintbinary(int[] arr, intx)
{
intstart = 0;
intend = arr.Length - 1;
while(start <= end) {
intmid = (start + end) / 2;
if(x == arr[mid]) {
returnmid;
}
elseif(x > arr[mid]) {
start = mid + 1;
}
else{
end = mid - 1;
}
}
return-1;
}
// Driver Code
publicstaticvoidMain(string[] args){
int[] arr = { 2, 4, 5, 17, 14, 7, 11, 22 };
intsearch = binary(arr, 22);
Console.Write(search);
}
}
// This code is contributed by aditya942003patil
Javascript
<script>
functionbinarySearch(array, x, low, high){
while(low <= high){
let mid = low + Math.floor((high - low)/2);
if(array[mid] == x)
returnmid;
elseif(array[mid] < x)
low = mid + 1;
else
high = mid - 1;
}
return-1;
}
let array = [2, 4, 5, 17, 14, 7, 11, 22];
let x = 22;
let result = binarySearch(array, x, 0, array.length-1);
if(result != -1)
console.log(result);
else
console.log("Not found");
// The code is constributed by Nidhi goel
</script>
Output
7
Time Complexity: O(log n) – Binary search algorithm divides the input array in half at every step, reducing the search space by half, and hence has a time complexity of logarithmic order. Auxiliary Space: O(1) – Binary search algorithm requires only constant space for storing the low, high, and mid indices, and does not require any additional data structures, so its auxiliary space complexity is O(1).
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
