DEV Community

Cover image for DSA & Searching Methods: Refresher for Coding Interview
Ryoichi Homma
Ryoichi Homma

Posted on

DSA & Searching Methods: Refresher for Coding Interview

#datastructures #algorithms #dsa #searchingmethods

Since I prepare for upcoming coding interviews, I've decided to revisit the core concepts of Data Structures and Algorithms (DSA). This article will be the second refresher to me where I'll explain searching methods for DSA. Whether you're revising for interviews or brushing up on your fundamentals, I hope you find this helpful!

Searching Methods

Searching is about finding the required data in a structure. Here are the most common search algorithms.

1. Linear Search

  • Description: traverse the list one element at a time.
  • Time Complexity: O(n).
  • Use Case: unsorted arrays, small data sets. 
function linearSearch(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) {
      return i; 
    } 
  }
  return -1; 
} 

// return 1 because 5 can be found in array at the index of 1.
console.log(linearSearch([3, 5, 7], 5)); 

// return 0 because 3 can be found in array at the index of 0.
console.log(linearSearch([3, 5, 7], 3)); 

// return -1 because 0 cannot be found in array.
console.log(linearSearch([3, 5, 7], 0));
Enter fullscreen mode Exit fullscreen mode

2. Binary Search (Iterative)

  • Description: divide the sorted list into half to find the element.
  • Time Complexity: O(log n).
  • Use Case: efficient lookup in sorted collections.

Note: Array must be sorted.

function binarySearch(arr, target) {
  let left = 0;  
  let right = arr.length - 1; 

  while (left <= right) {
    let mid = Math.floor((left + right) / 2);

    if (arr[mid] === target) {
      return mid; 
    } else if (arr[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }

  return -1; 
} 

// return 3 because 7 can be found in array at the index of 3. 
console.log(binarySearch([1, 3, 5, 7, 9], 7));

// return -1 because 0 cannot be found in array. 
console.log(binarySearch([1, 3, 5, 7, 9], 0));

// return 0 because 1 can be found in array at the index of 1. 
console.log(binarySearch([1, 3, 5, 7, 9], 1));
Enter fullscreen mode Exit fullscreen mode

3. Depth-First Search (DFS)

  • Description: explores as deep as possible along a branch before backtracking.
  • Time Complexity: O(V + E) (vertices + edges).
  • Use Case: graphs, trees, maze solving, topological sort. 
function dfs(graph, node, visited = new Set()) {
  if (visited.has(node)) {
    return; 
  }

  visited.add(node); 
  console.log(node); // current node

  for (let neighbor of graph.get(node)) {
    if (!visited.has(neighbor)) {
         dfs(graph, neighbor, visited); 
    }
  }
}
Enter fullscreen mode Exit fullscreen mode

4. Breadth-First Search (BFS)

  • Description: explores all neighbors before going deeper.
  • Time Complexity: O(V + E).
  • Used Case: shortest path in unweighted graphs, level-order tree traversal. 
function bfs(graph, start) {
  const visited = new Set();  
  const queue = [start]; 

  while (queue.length > 0) {
    const node = queue.shift(); // take out from queue

    if (!visited.has(node)) {
      console.log(node); // current node
      visited.add(node); 

      for (let neighbor of graph.get(node)) {
        if (!visited.has(neighbor)) {
          queue.push(neighbor); 
        }
      }
    }
  }
}
Enter fullscreen mode Exit fullscreen mode

5. Binary Search Tree Search

  • Description: traverse the BST left or right depending on the value.
  • Time Complexity: O(log n) average, O(n) worst (unbalanced tree).
  • Use Case: dynamic sets, range queries. 
function searchBST(node, value) {
  if (node === null) {
     return null; 
  }

  if (value === node.value) {
    return node; // if found
  }

  if (value < node.value) {
    return searchBST(node.left, value); // let smaller node to be left
  } else {
    return searchBST(node.right, value); // let bigger node to be right
  } 
}
Enter fullscreen mode Exit fullscreen mode

6. Hash-Based Search

  • Description: use a hash function to find the index.
  • Time Complexity: O(1) average.
  • Use Case: fast key-value lookup, duplicates detection. 
const map = new Map(); 
map.set("apple", 10); 
map.set("banana", 5); 

if (map.has("apple")) {
  console.log("Found", map.get("apple")); // return 10
} else {
  console.log("Not Found"); 
}
Enter fullscreen mode Exit fullscreen mode

Upcoming Posts

This article refreshes my DSA knowledge. In upcoming posts, I'll explore sorting algorithms in more details.
If you're also preparing for coding interviews or learning DSA, follow for more practical and concise DSA content. Feel free to leave comments for any questions!

Top comments (1)

Collapse
 
ghost_engineer_2883a1ca0a profile image
Ghost Engineer •

try this if you get stuck during the interview. its an AI co-pilot that solves the questions for you so you can focus on the more important part of the interview, the communication part. its also a really good study tool: ghostengineer.com

Some comments may only be visible to logged-in visitors. Sign in to view all comments. Some comments have been hidden by the post's author - find out more