Binary Search

Intro

A common pattern, that utilizes a start and end pointer to half the list or array step by step.

// For binarysearchtree see Trees.

How it works

1. Start by checking if middle element is the target
   1. If yes then success and return
2. If target is greater than middle, then set the start ptr to the element at the index of the middle + 1.
3. If target is less than middle, then set the end ptr to the element at the index of the middle - 1.

Since we’re halving the search zone each time, it’s very efficient, with a time complexity of O(log(n))

Binary Search and Monotonic Functions

Can be used on any collection that utilizes a monotonicfunction (function that either always increases or always decreases (or remains constant) over its entire domain) so can be used on any condition used for sorting, not just numbers.

Simple Iterative Implementation

class Solution {
    /**
     * @param {number[]} nums
     * @param {number} target
     * @return {number}
     */
    search(nums, target) {
        if(nums.length === 0){
            return -1;
        }
 
        let start = 0;
        let end = nums.length - 1;
        while(start <= end){
            let mid = Math.ceil(start + (end - start) / 2);
            if(nums[mid] < target){
                start = mid + 1;
            }
            else if(target < nums[mid]){
                end = mid - 1;
            }
            else{
                return mid;
            }
        }
        return -1;
        }
}

Blueprint to Deeper Understanding

Despite it’s simplicity there are a few places where configuring this algorithm to a specific problem can break.

1. Initializing the start and end variables
2. The while-loop condition, start < end or start <= end
3. How to update the pointers, search window. start = mid , start = mid + 1 and end = mid, end = mid - 1?

Zhijun’s Template

I’ve linked an article by Zhijun Liao that details how he applied bst to various problems by abstracting it.
His template is basically the same as most BST implementations but but written in a way that always considers adapting it.

Here it is:

def binary_search(array) -> int:
    def condition(value) -> bool:
        pass
 
    left, right = min(search_space), max(search_space) # could be [0, n], [1, n] etc. Depends on problem
    while left < right:
        mid = left + (right - left) // 2
        if condition(mid):
            right = mid
        else:
            left = mid + 1
    return left

He emphasizes that only three parts need modifying accordingly.

• The pointer initialization, based on the search space.
• Deciding if return left or left - 1 such that left is the min satisfying element for our condition predicate.
• Designing the condition predicate.
  Then gives some examples on how he used it.
  I think this is a good resource!

Recursive Implementation

At some point in my studies I was asked to do this recursively. No fuss, it’s the same algorithm, but instead of updating pointers, you’re making a recursive call while updating pointers. I’ve also done this in ocaml where the function had to be tail recursive but forgot how I did that, so instead we’re going to be simple folk and pass the pointers as you would an accumulator…

Breakdown:

• The base cases are self explanatory
• The rest is the same as before, but instead of updating the start and end we and loop we do so in the recursive call.
  Code:

def search(self, nums, start, end, target):
	"""
	:param start: int
	:param end: int
	:type nums: List[int]
	:type target: int
	:rtype: int
	"""
	if nums is None or len(nums) == 0:
		return -1
	elif len(nums) == 1:
		return 0
 
	mid = start + (end - start) // 2
	if nums[mid] < target:
		return self.search(nums, mid + 1, end, target)
	elif target < nums[mid]:
		return self.search(nums, start,mid - 1, target)
	else:
		return mid

Examples

Array examples:

• Binary Search
• First Bad Version

---

References

• Powerful Ultimate Binary Search Template by zhijun_liao