Searching and Binary Search | Skilled.dev
Learn

Searching and Binary Search

Course launching August 2020

Follow me on YouTube for free coding interview videos.

Users who sign up for the email list will receive an exclusive 75% discount at launch.

Your subscription could not be saved. Please try again.
Your subscription was successful! 🤓

Searching in interviews refers to finding an item in a data structure (and this item may or may not actually exist). In this article we'll be focusing on searching linear data structures like arrays, and then in the tree and graph sections, you'll expand on the concepts learned here binary search trees, depth first search, and breadth first search.

Cheat Sheet

Big O Complexity
search (sorted)O(log n)
search (unsorted)O(n)

Searching in Interviews

  • Unique binary search examples (rotated array, sparse array, no max size)
  • Compare multiple sorted arrays (ie. find median of two sorted arrays)
  • Search a matrix
  • Find duplicates

Binary Search

Given an array, the most straightforward way to search it is linearly where you just look for an item.

(show linear search of sorted and then show how it can be improved).

This is O(n) time and would be no different for something like a string or linked list. You just pass over every item until you find it.

Binary search is basically searching with super powers and gives us O(log n) time.

The most important constraint for binary search to work: the data must be sorted/order.

Since it's ordered

Prev
Logarithms and Time Complexity
Next
Sorting

Table of Contents