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, Inplace 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
nums
are unique.  n will be in the
range [1, 10000]
.  The value of each element in
nums
will 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 thattarget
will be smaller than all the numbers after indexmid
as the array is sorted in the ascending order. We can reduce our search toend = mid  1
. 
If
target > nums[mid]
, then we can conclude thattarget
will be greater than all numbers before indexmid
as 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.