Searching Algorithms

Searching algorithms are fundamental in computer science and are widely used in Leetcode problems. They are used to find the presence or position of a target value within a collection of data.

Table of Contents

• Table of Contents
• Searching Basics
• Common Searching Algorithms
  • 1. Linear Search
  • 2. Binary Search
  • 3. Depth-First Search (DFS)
  • 4. Breadth-First Search (BFS)
• Time and Space Complexity
• Related Leetcode Questions
  • Easy
  • Medium
  • Hard

Searching Basics

• Definition: Searching is the process of finding a specific element in a collection of data.
• Key Characteristics:
  • Linear Search: Searches the collection sequentially.
  • Binary Search: Searches a sorted collection by repeatedly dividing the search interval in half.

Common Searching Algorithms

1. Linear Search

• Algorithm: Sequentially checks each element of the collection until the target element is found.
• Example:

  public int linearSearch(int[] arr, int target) {
      for (int i = 0; i < arr.length; i++) {
          if (arr[i] == target) {
              return i;
          }
      }
      return -1;
  }

• Time Complexity: O(n)
• Space Complexity: O(1)

2. Binary Search

• Algorithm: Searches a sorted collection by repeatedly dividing the search interval in half. If the target value is less than the middle element, the search continues in the left half; otherwise, it continues in the right half.
• Example:

  public 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;
          } else if (arr[mid] < target) {
              left = mid + 1;
          } else {
              right = mid - 1;
          }
      }
      return -1;
  }

• Time Complexity: O(log n)
• Space Complexity: O(1)

3. Depth-First Search (DFS)

• Algorithm: Explores as far as possible along each branch before backtracking. Commonly used for searching in graphs or trees.
• Example:

  public void dfs(int node, boolean[] visited, List<List<Integer>> adjList) {
      visited[node] = true;
      System.out.println(node);
      for (int neighbor : adjList.get(node)) {
          if (!visited[neighbor]) {
              dfs(neighbor, visited, adjList);
          }
      }
  }

• Time Complexity: O(V + E) (where V is the number of vertices and E is the number of edges)
• Space Complexity: O(V)

4. Breadth-First Search (BFS)

• Algorithm: Explores all neighbors at the present depth before moving on to nodes at the next depth level. Commonly used for searching in graphs or trees.
• Example:

  public void bfs(int start, List<List<Integer>> adjList) {
      boolean[] visited = new boolean[adjList.size()];
      Queue<Integer> queue = new LinkedList<>();
      queue.add(start);
      visited[start] = true;
      while (!queue.isEmpty()) {
          int node = queue.poll();
          System.out.println(node);
          for (int neighbor : adjList.get(node)) {
              if (!visited[neighbor]) {
                  visited[neighbor] = true;
                  queue.add(neighbor);
              }
          }
      }
  }

• Time Complexity: O(V + E) (where V is the number of vertices and E is the number of edges)
• Space Complexity: O(V)

Time and Space Complexity

Algorithm	Time Complexity	Space Complexity
Linear Search	O(n)	O(1)
Binary Search	O(log n)	O(1)
DFS	O(V + E)	O(V)
BFS	O(V + E)	O(V)

Related Leetcode Questions

Easy

1. Binary Search
2. First Bad Version
3. Search Insert Position

Medium

1. Find First and Last Position of Element in Sorted Array
2. Search in Rotated Sorted Array
3. Kth Smallest Element in a BST

Hard

1. Median of Two Sorted Arrays
2. Word Ladder
3. Sliding Puzzle