Rocket Academy Bootcamp
  • 🚀Welcome to Bootcamp!
  • 🛠️Logistics
    • Course Schedules
    • Course Methodology
    • Required Software
    • LinkedIn Education Badge
  • 📚General Reference
    • Naming, Casing, and Commenting Conventions
    • VS Code Tips
    • Recommended Resources
  • 🪨0: Foundations
    • 0.1: Command Line
    • 0.2: Git
      • 0.2.1: Branches
    • 0.3: GitHub
      • 0.3.1: Pull Requests
    • 0.4: JavaScript
      • 0.4.1: ES6
      • 0.4.2: Common Syntax
      • 0.4.3: Reference vs Value
      • 0.4.4: Classes
      • 0.4.5: Destructuring and Spread Operator
      • 0.4.6: Promises
        • 0.4.6.1: Async Await
    • 0.5: Node.js
      • 0.5.1: Node Modules
      • 0.5.2: NPM
      • 0.5.3: Nodemon
  • 🖼️1: Frontend
    • 1.1: HTML
    • 1.2: CSS
      • 1.2.1: Layout
    • 1.3: React
      • Styling in ReactJs
      • Using Styling Libraries with React
      • React Deployment
    • 1.E: Exercises
      • 1.E.1: Recipe Site
      • 1.E.2: Portfolio Page
      • 1.E.3: World Clock
      • 1.E.4: High Card
      • 1.E.5: Guess The Word
    • 1.P: Frontend App
  • 🏭2: Full Stack
    • 2.1: Internet 101
      • 2.1.1: Chrome DevTools Network Panel
      • 2.1.2: HTTP Requests and Responses
    • 2.2: Advanced React
      • 2.2.1: AJAX
      • 2.2.2: React Router
      • 2.2.3: useContext
      • 2.2.4: useReducer
      • 2.2.5: Environmental Variables
      • 2.2.6: React useMemo - useCallback
    • 2.3: Firebase
      • 2.3.1: Firebase Realtime Database
      • 2.3.2: Firebase Storage
      • 2.3.3: Firebase Authentication
      • 2.3.4: Firebase Hosting
      • 2.3.5: Firebase Techniques
    • 2.E: Exercises
      • 2.E.1: Weather App
      • 2.E.2: Instagram Chat
      • 2.E.3: Instagram Posts
      • 2.E.4: Instagram Auth
      • 2.E.5: Instagram Routes
    • 2.P: Full-Stack App (Firebase)
  • 🤖3: Backend
    • 3.1: Express.js
      • 3.1.1 : MVC
    • 3.2: SQL
      • 3.2.1: SQL 1-M Relationships
      • 3.2.2: SQL M-M Relationships
      • 3.2.3: SQL Schema Design
      • 3.2.4: Advanced SQL Concepts
      • 3.2.5: SQL - Express
      • 3.2.6: DBeaver
    • 3.3: Sequelize
      • 3.3.1: Sequelize One-To-Many (1-M) Relationships
      • 3.3.2: Sequelize Many-To-Many (M-M) Relationships
      • 3.3.3: Advanced Sequelize Concepts
      • 3.3.4 Database Design
    • 3.4: Authentication
      • 3.4.1: JWT App
    • 3.5: Application Deployment
    • 3.E: Exercises
      • 3.E.1: Bigfoot JSON
      • 3.E.2: Bigfoot SQL
      • 3.E.3: Bigfoot SQL 1-M
      • 3.E.4: Bigfoot SQL M-M
      • 3.E.5: Carousell Schema Design
      • 3.E.6: Carousell Auth
    • 3.P: Full-Stack App (Express)
  • 🏞️4: Capstone
    • 4.1: Testing
      • 4.1.1: Frontend React Testing
      • 4.1.2: Backend Expressjs Testing
    • 4.2: Continuous Integration
      • 4.2.1 Continuous Deployment (Fly.io)
      • 4.2.2: Circle Ci
    • 4.3: TypeScript
    • 4.4: Security
    • 4.5: ChatGPT for SWE
    • 4.6: Soft Skills for SWE
    • 4.P: Capstone
  • 🧮Algorithms
    • A.1: Data Structures
      • A.1.1: Arrays
        • A.1.1.1: Binary Search
        • A.1.1.2: Sliding Windows
      • A.1.2: Hash Tables
      • A.1.3: Stacks
      • A.1.4: Queues
      • A.1.5: Linked Lists
      • A.1.6: Trees
      • A.1.7: Graphs
      • A.1.8: Heaps
    • A.2: Complexity Analysis
    • A.3: Object-Oriented Programming
    • A.4: Recursion
    • A.5: Dynamic Programming
    • A.6: Bit Manipulation
    • A.7: Python
  • 💼Interview Prep
    • IP.1: Job Application Strategy
    • IP.2: Resume
    • IP.3: Portfolio
Powered by GitBook
On this page
  • Learning Objectives
  • Introduction
  • Example Code
  • Exercises
  • Pre-Class
  • Part 1
  1. Algorithms
  2. A.1: Data Structures
  3. A.1.1: Arrays

A.1.1.1: Binary Search

PreviousA.1.1: ArraysNextA.1.1.2: Sliding Windows

Learning Objectives

  1. Understand conceptually how binary search works

  2. Know how to implement binary search in code

Introduction

Binary search allows us to search a sorted array for a target number in O(logn) time. The following videos explain the concept.

Example Code

Consider the following canonical binary search implementation.

const binarySearch = (arr, x) => {
  // Initialise left and right bounds of search to start and end of arr
  let left_index = 0;
  let right_index = arr.length - 1;
  // While left_index and right_index have yet to overlap
  while (left_index <= right_index) {
    // Find the midpoint between left_index and right_index
    let mid_index = Math.floor((left_index + right_index) / 2);

    console.log("middle index", mid_index);
    // If the element at mid_index is x, return mid_index
    // Use Math.floor to ensure that the index position is an integer not a decimal
    if (arr[mid_index] === x) {
      return mid_index;
    }
    // Otherwise, if x is greater than elem at mid_index,
    // update left_index to be 1 above mid_index
    else if (arr[mid_index] < x) {
      left_index = mid_index + 1;
    }
    // Otherwise, if x is less than elem at mid_index,
    // update right_index to be 1 below mid_index
    else {
      right_index = mid_index - 1;
    }
  }
  // If x is not found, return -1
  return -1;
};

const myList = [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12];
const result = binarySearch(myList, 6); // 4
console.log(result);

Exercises

After attempting each problem, find solutions in the Leaderboard tab (HackerRank, may be on left side of page) or Solution or Discuss tabs (LeetCode) on that problem's page. If you get stuck for more than 15 minutes, review and understand the solutions and move on. Come back and re-attempt the problem after a few days.

Pre-Class

Part 1

Binary Search ()

(Python)

(Python)

First Bad Version ()

Valid Perfect Square ()

Search Insert Position ()

Two Sum II Input Array is Sorted ()

Count Negative Numbers in a Sorted Matrix ()

(Python)

(Python)

🧮
LeetCode
Rocket solution code
Rocket solution video
LeetCode
LeetCode
LeetCode
LeetCode
LeetCode
Rocket solution code
Rocket solution video
Dramatic illustration of the efficiency of binary search
Explanation of the binary search algorithm in code and its runtime