Coding Patterns: Modified Binary Search
In Coding Patterns series, we will try to recognize common patterns underlying behind each algorithm question, using real examples from Leetcode.
Previous posts were about Sliding Window, Two Pointers, Fast & Slow Pointers, Merge Intervals, Cyclic Sort, In-place Reversal of a Linked List, Breadth First Search (BFS), Depth First Search (DFS), Two Heaps and Subsets patterns and today, we will introduce Modified Binary Search pattern which is very useful to solve the problems whenever we are given a sorted Array or Linked List or Matrix, and we are asked to find a certain element.
This pattern describes an efficient way to handle all problems involving Binary Search.
Problem: Binary Search
LeetCode 704 - Binary Search [easy]
Given a sorted (in ascending order) integer array nums of n elements and a target value, write a function to search target in nums. If target exists, then return its index, otherwise return -1.
Example 1:
Input: nums = [-1, 0, 3, 5, 9, 12], target = 9
Output: 4
Explanation: 9 exists in nums and its index is 4
Example 2:
Input: nums = [-1, 0, 3, 5, 9, 12], target = 2
Output: -1
Explanation: 2 does not exist in nums so return -1
Note:
- You may assume that all elements in
numsare unique. - n will be in the
range [1, 10000]. - The value of each element in
numswill be in therange [-9999, 9999].
Binary Search Solution
1- Let’s assume that start is the first element and end is the last element in nums.
start = 0
end = len(nums) - 1
2- We need to find middle value, mid. An easy way to do it in Python is
mid = (start + end) // 2
For Java and C++, this equation will work for most cases, but when start or end is large, this equation will give us the wrong result due to integer overflow. To solve this problem, we will do our calculation a bit differently;
int mid = start + (end - start) / 2;
3- Next, we will see if the target value is equal to the number at mid value. If it is equal we return mid as the required index.
4- If target is not equal to number at index mid, there are two possibilities that we need to check:
-
If
target < nums[mid], then we can conclude thattargetwill be smaller than all the numbers after indexmidas the array is sorted in the ascending order. We can reduce our search toend = mid - 1. -
If
target > nums[mid], then we can conclude thattargetwill be greater than all numbers before indexmidas the array is sorted in the ascending order. We can reduce our search tostart = mid + 1.
from typing import List
class Solution:
def search(self, nums: List[int], target: int) -> int:
start, end = 0, len(nums) - 1
while start <= end:
mid = (start + end) // 2
if target == nums[mid]:
return mid
if target < nums[mid]:
end = mid - 1
else:
start = mid + 1
return -1
Time Complexity: O(log N) where N is the total elements in the given array.
Space Complexity: O(1)
How to identify?
This approach is quite useful to solve the problems whenever we are given a sorted Array or Linked List or Matrix, and we are asked to find a certain element.
This pattern describes an efficient way to handle all problems involving Binary Search.