Data Structures
Search in Rotated Sorted Array II (With Duplicates)
Search in Rotated Sorted Array II (LeetCode 81) with duplicates: binary search that shrinks ambiguous ends, O(log n) average and O(n) worst case.
#Searching
30 notes tagged
Data Structures
Search in Rotated Sorted Array
Search in Rotated Sorted Array (LeetCode 33): modified binary search that identifies the sorted half each step, in O(log n).
Data Structures
First and Last Position of Element in Sorted Array
Find First and Last Position of a target in a sorted array (LeetCode 34) using two binary searches (lower and upper bound) in O(log n).
Data Structures
Search Insert Position
Search Insert Position (LeetCode 35): use lower-bound binary search to find where a target is or should be inserted, in O(log n).
Data Structures
Binary Search (Recursive)
Recursive binary search on a sorted array in O(log n) time with O(log n) call-stack space, in Python, Java and C++.
Data Structures
Binary Search (Classic Iterative)
Classic iterative binary search on a sorted array in O(log n) time, with Python, Java and C++ code and an overflow-safe midpoint.