On Your Right
Searching Algorithms: Binary Search — Technique II
This technique is an advanced form of Binary Search used to search an array for an element or condition which requires:
accessing the current index AND its immediate right neighbor’s index.
This technique uses the element’s right neighbor to determine if the condition is met and to decide to go left or right. It also guarantees that the searchable subsection has at least a size of 2 at each step.
Right On — Distinguishing Syntax
- Initial Condition:
left = 0, right = nums.length - Termination:
left === right - Searching Left:
right = mid - Searching Right:
left = mid + 1
That’s Right — Post-Processing
Generally, Binary Search is composed of 3 main sections:
- Pre-processing: Sort if the collection is unsorted
- Binary Search: Using a loop or recursion to divide search space in half after each comparison
- Post-processing: Determine viable candidates in the remaining space
Unlike Technique I, Technique II usually requires post-processing. Since the loop or recursion ends when there is 1 element left (left === right), you need to assess if the remaining element meets the condition. In other words: If the element that meets the condition is not returned from the loop or recursion, the remaining element (nums[left]) needs to be evaluated to see if it meets the condition.
// Post-processing// End Condition: left === rightif(left !== nums.length && nums[left] === target) return leftreturn -1
All The Right Moves
JavaScript Example
Sample Problems
📚 Resources 👀
Leetcode Explore: Binary Search — Template II
First Bad Version | LeetCode 278 | Facebook Coding Interview Tutorial
