40
Searching Algorithms
Searching algorithms is a basic, fundamental step in computing done via a step-by-step method to locate specific data among a collection of data.
What is a Search Algorithm?
According to Wikipedia- Search algorithm is-
Any algorithm which solves the search problem, namely, to retrieve information stored within some data structure, or calculated in the search space of a problem domain, either with discrete or continuous values.
They are designed to check or retrieve an element from any data structure where it is being stored. They search for a target (key) in the search space.
Types of Searching Algorithms
In this post, we are basically going to discuss two important algorithms -
Let us discuss these two in detail with examples, code implementation, and time complexity analysis.
Linear or Sequential Search
This algorithm works by sequentially iterating through the whole array or list from one end until the target element is found. If the element is found, it returns its index, else -1.
Now let us take an example and try to understand :
arr = [2, 12, 15, 11, 7, 19, 45]
Suppose, the target element to be searched is
7
.Approach :
Code Implementation
In Java
package algorithms.searching;
public class LinearSearch {
public static void main(String[] args) {
int[] nums = {2, 12, 15, 11, 7, 19, 45};
int target = 7;
System.out.println(search(nums, target));
}
static int search(int[] nums, int target) {
for (int index = 0; index < nums.length; index++) {
if (nums[index] == target) {
return index;
}
}
return -1;
}
}
In Python
def search(nums, target):
for i in range(len(nums)):
if nums[i] == target:
return i
return -1
if __name__ == '__main__':
nums = [2, 12, 15, 11, 7, 19, 45]
target = 7
print(search(nums, target))
Time Complexity Analysis
O(1)
.O(N)
(the constant being ignored).O(N)
.Binary Search
This type of searching algorithm is used to find the position of a specific value contained in a sorted array. The binary search algorithm works on the principle of divide & conquer and it is considered the best searching algorithm because of its faster speed to search.
Now let us take a sorted array as an example and try to understand :
arr = [2, 12, 15, 17, 27, 29, 45]
Suppose, the target element to be searched is 1
7
.Approach
Code Implementation
In Java
package algorithms.searching;
public class BinarySearch {
public static void main(String[] args) {
int[] nums = {2, 12, 15, 17, 27, 29, 45};
int target = 17;
System.out.println(search(nums, target));
}
static int search(int[] nums, int target) {
int start = 0;
int end = nums.length - 1;
while (start <= end) {
int mid = start + (end - start) / 2;
if (nums[mid] > target)
end = mid - 1;
else if (nums[mid] < target)
start = mid + 1;
else
return mid;
}
return -1;
}
}
In Python
def search(nums, target):
start = 0
end = len(nums)-1
while start <= end:
mid = start + (end-start)//2
if nums[mid] > target:
end = mid-1
elif nums[mid] < target:
start = mid+1
else:
return mid
return -1
if __name__ == '__main__':
nums = [2, 12, 15, 17, 27, 29, 45]
target = 17
print(search(nums, target))
Time Complexity Analysis
O(1)
.O(logN)
O(logN)
Calculating Time complexity:
Length of array = N
Length of array = N/2
Length of array = (N/2)/2 = N/2^2
Length of array = N/2^k
Length of array = N⁄2k = 1 => N = 2k
=> log2 (N) = log2 (2k) => log2 (N) = k log2 (2)
=> k = log2 (N)
Hence, the time complexity of Binary Search is log2 (N)
You can also visualise the above two algorithms using the simple tool built by Dipesh Patil - Algorithms Visualiser
Order-agnostic Binary Search
Suppose, we have to find a target element in a sorted array. Though we know that the array is sorted, we don’t know if it’s sorted in ascending or descending order.
Approach
The implementation is similar to binary search except that we need to identify whether the array is sorted in ascending order or descending order to make the decision about whether to continue the search in the left half of the array or the right half of the array.
end=mid-1
.start=mid+1
The only thing we need to do is to figure out whether the array is sorted in ascending order or descending order. We can easily find this by comparing the first and last elements of the array.
if arr[0] < arr[arr.length-1]
array is sorted in ascending order
else
array is sorted in descending order
Code Implementation
In Java
package algorithms.searching;
public class OrderAgnosticBinarySearch {
public static void main(String[] args) {
int[] nums1 = {-1, 2, 4, 6, 7, 8, 12, 15, 19, 32, 45, 67, 99};
int[] nums2 = {99, 67, 45, 32, 19, 15, 12, 8, 7, 6, 4, 2, -1};
int target = -1;
System.out.println(search(nums1, target));
System.out.println(search(nums2, target));
}
static int search(int[] arr, int target) {
int start = 0;
int end = arr.length - 1;
boolean isAscending = arr[start] < arr[end];
while (start <= end) {
int mid = start + (end - start) / 2;
if (target == arr[mid])
return mid;
if (isAscending) {
if (target < arr[mid]) {
end = mid - 1;
} else {
start = mid + 1;
}
} else {
if (target < arr[mid]) {
start = mid + 1;
} else {
end = mid - 1;
}
}
}
return -1;
}
}
In Python
def search(nums, target):
start = 0
end = len(nums)-1
is_ascending = nums[start] < nums[end]
while start <= end:
mid = start + (end-start)//2
if target == nums[mid]:
return mid
if is_ascending:
if target < nums[mid]:
end = mid-1
else:
start = mid+1
else:
if target < nums[mid]:
start = mid+1
else:
end = mid-1
return -1
if __name__ == '__main__':
nums1 = [-1, 2, 4, 6, 7, 8, 12, 15, 19, 32, 45, 67, 99]
nums2 = [99, 67, 45, 32, 19, 15, 12, 8, 7, 6, 4, 2, -1]
target = -1
print(search(nums1, target))
print(search(nums2, target))
Time Complexity Analysis
There will be no change in the time complexity and hence will be the same as Binary Search.
Conclusion
In this blog, we discussed the two most important searching algorithms. This blog post cannot end without thanking the person who has motivated a lot of students to learn DSA, that too free of cost - Kunal Kushwaha and Community Classroom. You can also access his free DSA playlist here.
I will also soon be publishing it on GeeksforGeeks.
I will also soon be publishing it on GeeksforGeeks.
40