- Data Structures & Algorithms
- DSA - Home
- DSA - Introduction
- DSA - Environment Setup
- DSA - Algorithms Basics
- DSA - Characteristics of Algorithms
- DSA - Asymptotic Analysis
- Data Structures
- DSA - Data Structure Basics
- DSA - Data Structures and Types
- DSA - Array Data Structure
- Linked Lists
- DSA - Linked List Data Structure
- DSA - Single Linked List Data Structure
- DSA - Doubly Linked List Data Structure
- DSA - Circular Linked List Data Structure
- Stack & Queue
- DSA - Stack Data Structure
- DSA - Expression Parsing
- DSA - Queue Data Structure
- Searching Algorithms
- DSA - Searching Algorithms
- DSA - Linear Search Algorithm
- DSA - Binary Search Algorithm
- DSA - Interpolation Search
- DSA - Jump Search Algorithm
- DSA - Exponential Search
- DSA - Fibonacci Search
- DSA - Sublist Search
- DSA - Hash Table
- Sorting Algorithms
- DSA - Sorting Algorithms
- DSA - Bubble Sort Algorithm
- DSA - Insertion Sort Algorithm
- DSA - Selection Sort Algorithm
- DSA - Merge Sort Algorithm
- DSA - Shell Sort Algorithm
- DSA - Heap Sort
- DSA - Bucket Sort Algorithm
- DSA - Counting Sort Algorithm
- DSA - Radix Sort Algorithm
- DSA - Quick Sort Algorithm
- Graph Data Structure
- DSA - Graph Data Structure
- DSA - Depth First Traversal
- DSA - Breadth First Traversal
- DSA - Spanning Tree
- Tree Data Structure
- DSA - Tree Data Structure
- DSA - Tree Traversal
- DSA - Binary Search Tree
- DSA - AVL Tree
- DSA - Red Black Trees
- DSA - B Trees
- DSA - B+ Trees
- DSA - Splay Trees
- DSA - Tries
- DSA - Heap Data Structure
- Recursion
- DSA - Recursion Algorithms
- DSA - Tower of Hanoi Using Recursion
- DSA - Fibonacci Series Using Recursion
- Divide and Conquer
- DSA - Divide and Conquer
- DSA - Max-Min Problem
- DSA - Strassen's Matrix Multiplication
- DSA - Karatsuba Algorithm
- Greedy Algorithms
- DSA - Greedy Algorithms
- DSA - Travelling Salesman Problem (Greedy Approach)
- DSA - Prim's Minimal Spanning Tree
- DSA - Kruskal's Minimal Spanning Tree
- DSA - Dijkstra's Shortest Path Algorithm
- DSA - Map Colouring Algorithm
- DSA - Fractional Knapsack Problem
- DSA - Job Sequencing with Deadline
- DSA - Optimal Merge Pattern Algorithm
- Dynamic Programming
- DSA - Dynamic Programming
- DSA - Matrix Chain Multiplication
- DSA - Floyd Warshall Algorithm
- DSA - 0-1 Knapsack Problem
- DSA - Longest Common Subsequence Algorithm
- DSA - Travelling Salesman Problem (Dynamic Approach)
- Approximation Algorithms
- DSA - Approximation Algorithms
- DSA - Vertex Cover Algorithm
- DSA - Set Cover Problem
- DSA - Travelling Salesman Problem (Approximation Approach)
- Randomized Algorithms
- DSA - Randomized Algorithms
- DSA - Randomized Quick Sort Algorithm
- DSA - Karger’s Minimum Cut Algorithm
- DSA - Fisher-Yates Shuffle Algorithm
Data Structures & Algorithms - Searching Algorithms
 Share with a Friend |
Searching Algorithms
Searching algorithms are used to find an element or group of elements in a data structure like an array, list, or database.
Common Types of Searching Algorithms
1. Linear Search (Sequential Search)
- Description: Check each element in the list one by one until the target element is found or the list ends.
- Time Complexity: O(n)
- Use Case: Unsorted or small datasets.
2. Binary Search
- Description: Works on sorted arrays. Repeatedly divides the search interval in half, comparing the middle element to the target.
- Time Complexity: O(log n)
- Use Case: Large sorted datasets.
3. Interpolation Search
- Description: Improvement over binary search for uniformly distributed sorted data, estimating the position of the target based on the value.
- Time Complexity: O(log log n) average case.
- Use Case: Uniformly distributed sorted data.
4. Exponential Search
- Description: Useful for unbounded or infinite lists; finds range where the element may exist, then applies binary search.
- Time Complexity: O(log n)
- Use Case: Infinite or large sorted lists.
Detailed Explanation & Example: Linear Search
Algorithm:
- Start from the first element.
- Compare each element with the target.
- If match found, return index.
- If no match found, return -1.
Linear Search implementation - C, C++, Java, Python
#include <stdio.h>
int linearSearch(int arr[], int n, int target) {
for (int i = 0; i < n; i++) {
if (arr[i] == target) return i;
}
return -1;
}
int main() {
int arr[] = {10, 20, 30, 40, 50};
int n = sizeof(arr)/sizeof(arr[0]);
int target = 30;
int result = linearSearch(arr, n, target);
if (result != -1)
printf("Element found at index %d\n", result);
else
printf("Element not found\n");
return 0;
}
Output
Element found at index 2
#include <iostream>
using namespace std;
int linearSearch(int arr[], int n, int target) {
for (int i = 0; i < n; i++) {
if (arr[i] == target) return i;
}
return -1;
}
int main() {
int arr[] = {10, 20, 30, 40, 50};
int n = sizeof(arr)/sizeof(arr[0]);
int target = 30;
int result = linearSearch(arr, n, target);
if (result != -1)
cout << "Element found at index " << result << endl;
else
cout << "Element not found" << endl;
return 0;
}
Output
Element found at index 2
public class LinearSearch {
public static int linearSearch(int[] arr, int target) {
for (int i = 0; i < arr.length; i++) {
if (arr[i] == target)
return i;
}
return -1;
}
public static void main(String[] args) {
int[] arr = {10, 20, 30, 40, 50};
int target = 30;
int result = linearSearch(arr, target);
if (result != -1)
System.out.println("Element found at index " + result);
else
System.out.println("Element not found");
}
}
Output
Element found at index 2
def linear_search(arr, target):
for i, val in enumerate(arr):
if val == target:
return i
return -1
arr = [10, 20, 30, 40, 50]
target = 30
result = linear_search(arr, target)
if result != -1:
print(f"Element found at index {result}")
else:
print("Element not found")
Output
Element found at index 2
Detailed Explanation & Example: Binary Search
Algorithm:
- Find the middle element of the array.
- If middle element is equal to target, return index.
- If target is less, repeat search in left subarray.
- If target is greater, repeat search in right subarray.
- If subarray size reduces to zero, target is not found.
Binary Search implementation - C, C++, Java, Python
#include <stdio.h>
int binarySearch(int arr[], int n, int target) {
int left = 0, right = n -1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) return mid;
else if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}
int main() {
int arr[] = {10, 20, 30, 40, 50};
int n = sizeof(arr)/sizeof(arr[0]);
int target = 30;
int result = binarySearch(arr, n, target);
if (result != -1)
printf("Element found at index %d\n", result);
else
printf("Element not found\n");
return 0;
}
Output
Element found at index 2
#include <iostream>
using namespace std;
int binarySearch(int arr[], int n, int target) {
int left = 0, right = n - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) return mid;
else if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}
int main() {
int arr[] = {10, 20, 30, 40, 50};
int n = sizeof(arr)/sizeof(arr[0]);
int target = 30;
int result = binarySearch(arr, n, target);
if (result != -1)
cout << "Element found at index " << result << endl;
else
cout << "Element not found" << endl;
return 0;
}
Output
Element found at index 2
public class BinarySearch {
public static int binarySearch(int[] arr, int target) {
int left = 0, right = arr.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target)
return mid;
if (arr[mid] < target)
left = mid + 1;
else
right = mid - 1;
}
return -1;
}
public static void main(String[] args) {
int[] arr = {10, 20, 30, 40, 50};
int target = 30;
int result = binarySearch(arr, target);
if (result != -1)
System.out.println("Element found at index " + result);
else
System.out.println("Element not found");
}
}
Output
Element found at index 2
def binary_search(arr, target):
left, right = 0, len(arr) -1
while left <= right:
mid = left + (right - left) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
arr = [10, 20, 30, 40, 50]
target = 30
result = binary_search(arr, target)
if result != -1:
print(f"Element found at index {result}")
else:
print("Element not found")
Output
Element found at index 2
Summary Table
| Algorithm | Best Case | Worst Case | Average Case | Requires Sorted Data? | Use Case |
|---|---|---|---|---|---|
| Linear Search |
O(1) |
O(n) |
O(n) |
No |
Small or unsorted datasets |
| Binary Search |
O(1) |
O(log n) |
O(log n) |
Yes |
Large sorted datasets |
| Interpolation |
O(1) |
O(n) |
O(log log n) |
Yes |
Uniformly distributed data |
| Exponential |
O(1) |
O(log n) |
O(log n) |
Yes |
Infinite or unbounded sorted data |