Algorithms — Binary Search Template That Can Solve Lots of Problems

Discussing Binary Search, and how to use its template code with Two Pointers to solve multiple interview questions in C# for a better understanding of Data Structure and Algorithms.

Goal

The goal is to share some concise notes on Binary Search, and its implementation using both recursion and two pointers algorithm. Hopefully, the high-level summary notes allow you to add Binary Search to your tool bag without getting swamped by detailed textbook explanations. The following items are covered:

• Algorithm high-level logic
• Typical use cases/interview questions referencing LeetCode
• Typical bugs/gotchas in implementation

What is Binary Search?

Binary Search is an algorithm to search a sorted array for a target value. Important notes on Binary Search:

• O(logn) time complexity, as the problem size is reduced to half after each iteration
• O(1) space complexity
• works on sorted arrays

Classic interview questions on Binary Search:

• Find Position of Element in Sorted Array
• Find First Position of Element in Sorted Array
• Find Last Position of Element…