Home/Blog/Interview Prep/Explore the modified binary search algorithm for coding interview

Explore the modified binary search algorithm for coding interview

Q: What is a modified binary search?

A modified binary search adapts the standard binary search to solve specific problems, like finding an element’s first or last occurrence or searching in a rotated array.

Q: What is a binary search?

Binary search quickly locates an element in a sorted list by repeatedly dividing the search range in half until the element is found or no range remains.

Q: What are the different ways to implement binary search?

Binary search can be implemented in two main ways: iteratively and recursively. Both approaches use the same strategy of dividing the search space, but they differ in structure—one relies on loops, while the other uses function calls.

Q: What is the main condition of binary search?

The main condition for binary search is that the array or list must be sorted. This allows the algorithm to efficiently divide the search space and eliminate half of the elements in each step.

Q: What are the real-world uses of binary search?

Binary search is used in various real-world applications, such as searching large databases, finding elements in sorted collections, optimizing search algorithms in games, and solving problems like finding the square root or the shortest path in graphs.

Q: What is the main condition of a modified binary search?

In modified binary search, the search space is adjusted by checking which half of the array is sorted and then determining whether the target could be in that sorted half before proceeding.

8 min read

Nov 28, 2024

content

Linear search Binary search The time complexity of binary search Modified binary search Explanation with an example Additional problems solvable with modified binary search Test your understanding Moving forward

Have you ever thought about how search engines can instantly pull up the right results, or why so many coding interviews emphasize search problems? It all comes down to understanding search algorithms. Picture yourself flipping through a dictionary where the words aren’t alphabetically ordered—finding anything would be a nightmare, right? This is where efficient search techniques like binary search save the day. They help us quickly locate information across enormous datasets, whether you’re digging through files on your computer, querying a database, or browsing the internet. Mastering these algorithms is essential for any aspiring programmer, as the speed of search operations can make or break the performance of apps, websites, and software systems. Proficiency in these techniques is a must-have skill, frequently put to the test in technical interviews.

This blog will start by explaining the linear search algorithm, covering its basic principles, and providing a simple example to illustrate how it works. Next, we will move forward to the binary search algorithm, discussing its efficiency improvements over linear search and detailing the step-by-step process of how it operates. Finally, we will introduce a coding pattern that is a variant of the binary search called the Modified Binary Search algorithm, which addresses specific scenarios and enhances the functionality of the standard binary search.

Linear search#

Linear search involves examining each element in a list one by one until it locates the target value or reaches the end of the list. It starts from the beginning of the list and compares each element with the target value. If a match is found, the linear search returns the index of the target element; otherwise, it continues searching until the end of the list is reached and returns a value that is not a valid index, such as null, or -1.

Here‘s a basic Python code template for linear search:

Linear search is helpful when data isn’t organized in any specific order, unlike binary search, which requires data to be sorted beforehand. This is particularly useful when data changes often, as linear search doesn’t need the extra work of sorting data, which can be complicated and time-consuming for binary search. For smaller data sets prioritizing simplicity over speed, linear search offers a straightforward solution. However, for larger datasets where efficiency is important, binary search, despite requiring sorted data, is generally more suitable due to its faster performance.

Binary search#

Binary search is a more efficient searching algorithm compared to linear search, when working with sorted data. It operates by repeatedly dividing the search interval in half. Here’s how it works:

Initialization: Binary search begins by comparing the target value with the middle element of the sorted list.
Divide and conquer: If the target value matches the middle element, the search operation concludes successfully. If the target value is less than the middle element, the search continues in the lower half of the list. Conversely, the search proceeds in the upper half if the target value is greater.
Iterative process: This process is repeated until it finds the target value or finishes checking all potential positions in the list. Potential positions refer to all the places or indexes in the list where the target value could be found during the binary search process.

Here’s a self-explanatory Python template for the binary search algorithm:

def binary_search(array, value):
    start, end = 0, len(array) - 1
    
    while start <= end:
        middle = (start + end) // 2  # Calculate the middle index
        
        # Check if the value is present in the middle
        if array[middle] == value:
            return middle  # Return the index of the value
        
        # If value is greater, ignore the left half
        if array[middle] < value:
            start = middle + 1
        else:  # If value is smaller, ignore the right half
            end = middle - 1
    
    return -1  # Return -1 if the value is not found

Binary Search code template

The time complexity of binary search#

Each binary search step reduces the problem size by approximately half. It means that the number of steps required to reduce the problem size to 1 is $\log_2(n)$ , where $\log_2$ denotes the logarithm base 2. Therefore, the time complexity of binary search is $O(\log(n))$ .

This efficiency makes binary search particularly suitable for large datasets, where reducing the number of operations significantly improves performance.

Modified binary search#

Modified binary search is an advanced coding pattern that involves tweaking the traditional binary search algorithm to solve specific problems more efficiently. Unlike standard binary search, which focuses on finding an exact match, modified binary search adapts to handle variations, such as finding the peak element in a rotated sorted array or the maximum value in a bitonic array. This pattern typically involves adjusting the binary search logic to decide whether to move left or right based on specific conditions other than direct comparison with the target value.

Explanation with an example#

Now, to explain the modified binary search, let’s walk through an example and see how we modify the classical binary search to solve the Search in a Rotated Sorted Array problem. Consider the following problem statement for Search in a Rotated Array:

Given a sorted array of integers originally sorted in ascending order but then rotated at an unknown pivot, find the index of a given target value in the array.

If we want to apply classical binary search, the above problem cannot be solved because the entire array is not in ascending order. The array has been shifted left multiple times to achieve the effect of rotation at a pivot. To find the target, we adjust the binary search as follows to account for the rotation:

Start by initializing two pointers, start and end, at the beginning and end of the array.
Calculate the middle index mid and compare the target with the middle element.
Identify which half of the array is properly sorted as follows:
- If the element at the start of the array is less than or equal to the middle element, the left half is sorted.
- If the middle element is less than or equal to the element at the end of the array, the right half is sorted.
Determine if the target lies within the sorted half as follows:
- If the left half is sorted:
  - Check if the target is greater than or equal to the start element and less than or equal to the middle element.
  - If true, the target lies within the left half. Adjust the end index to mid - 1 to continue searching in the left half.
  - If false, the target is in the right half. Adjust the start index to mid + 1 to continue searching in the right half.
- If the right half is sorted:
  - Check if the target is greater than or equal to the middle element and less than or equal to the end element.
  - If true, the target lies within the right half. Adjust the start index to mid + 1 to continue searching in the right half.
  - If false, the target is in the left half. Adjust the end index to mid - 1 to continue searching in the left half.
Continue this process until the target is found or the search interval is empty.

def binary_search(nums, start, end, target):
    if (start > end):
        return -1
    mid = start + (end - start) // 2
    if nums[mid] == target:
        return mid
    if nums[start] <= nums[mid]:
        if nums[start] <= target and target < nums[mid]:
            return binary_search(nums, start, mid-1, target)
        return binary_search(nums, mid+1, end, target)
    else:
        if nums[mid] < target and target <= nums[end]:
            return binary_search(nums, mid+1, end, target)
        return binary_search(nums, start, mid-1, target)
def binary_search_rotated(nums, target):
    return binary_search(nums, 0, len(nums)-1, target)
def main():
    nums_list = [[5, 6, 7, 1, 2, 3, 4],
                 [40, 50, 60, 10, 20, 30],
                 [47, 58, 69, 72, 83, 94, 12, 24, 35], 
                 [77, 82, 99, 105, 5, 13, 28, 41, 56, 63], 
                 [48, 52, 57, 62, 68, 72, 5, 7, 12, 17, 21, 28, 33, 37, 41]]
    target_list = [1, 50, 12, 56, 5]
    for i in range(len(target_list)):
        print((i + 1), ".\tRotated array: ", nums_list[i], "\n\ttarget",
        target_list[i], "found at index ", \
              binary_search_rotated(nums_list[i], target_list[i]))
        print("-" * 100)
if __name__ == '__main__':
    main()

Coding Interview Preparation Course

Data Structures for Coding Interviews in Python

Data structures are amongst the most fundamental concepts of Computer Science. The data structure chosen can make or break an entire computer program. Consequently, they are also largely categorized as a vital benchmark of computer science knowledge when it comes to industry interviews. This course contains a detailed review of all the common data structures and provides implementation level details in Python to allow readers to become well equipped. Now with more code solutions, lessons, and illustrations than ever, this is the course for you!

30hrs

Beginner

65 Challenges

24 Quizzes

Problem	Statement	Solution Summary
First Bad Version	The latest version of a software product fails the quality check. Since each version builds on the previous one, all versions made after a bad version are also bad. You have n versions with IDs from 1 to n, and you can use an API function that returns TRUE if the version ID is bad. Find the first bad version that causes all later versions to be bad. The solution should also count and minimize the number of API calls made.	Starting with the entire range of versions, it checks the midpoint to determine if it is a bad version. If it is, the algorithm continues searching in the left half. Otherwise, it searches in the right half. This process continues until the first bad version is identified, ensuring an optimal time complexity of O(log n).
Find K Closest Elements	You are given a sorted array of integers, nums, and two integers, target, and k. Your task is to return k integers close to the target value. The integers in the output array should be in sorted order. An integer `nums[i]` is considered closer to the target compared to `nums[j]` when `\|nums[i] - target\| < \|nums[j] - target\|`. If `\|nums[i] - target\| = \|nums[j] - target\|`, the smaller value is selected.	First, use binary search to find the index of the closest integer to the target. Then, initialize two pointers to maintain a sliding window around this index. Adjust the pointers based on their distance to the target until the window size equals k. Finally, return the k elements within the window.
Single Element in a Sorted Array	You are given a sorted array of integers, `nums`, where all integers appear twice except for one. Your task is to find and return the single integer that appears only once.	When all elements appear in pairs, the first element of each pair is at an even index, and the second element is at an odd index. This pattern breaks at the point where the single non-duplicate element appears. Using the binary search with left and right pointers, compute the mid-index and make it even by decrementing it once if it’s odd. Check whether array[mid] equals array[mid + 1]. If they are the same, move the left pointer to mid + 2. If different, move the right pointer to mid. Finally, when the pointers converge, they will point to the single non-duplicate element, which is then returned as the output.

Match The Answer

Select an option from the left-hand side

Detect a cycle in a graph.

Modified binary search

Check if a number is the majority element in a sorted array.

Some other pattern

Find a peak element in an array strictly greater than its immediate left and right neighbors. Assume that adjacent elements in the array can never be equal.

Classical binary search

Given an integer array, return the smallest missing positive integer.

Find an element in a sorted integer array.

Moving forward#

If you're preparing for coding interviews, here's a roadmap to help you focus on the following three areas:

Data structures as a problem-solving prerequisite: Understanding fundamental data structures such as arrays, linked lists, trees, and graphs lays a strong foundation for effective problem-solving in coding interviews. Educative offers the course Data Structures for Coding Interviews which comprehensively covers all fundamental data structures essential for practicing and preparing for problem-solving questions. The course is available in C++, Python, Java, and JavaScript, allowing you to choose the language you’re most comfortable with.
Problem-solving with coding patterns: As previously mentioned, another highly recommended course is Educative's Grokking Coding Interview Patterns, which is available in six different programming languages. This comprehensive course covers 26 coding patterns, including the Modified Binary Search algorithm. Mastering these coding patterns will enhance your problem-solving skills and equip you with structured approaches that are crucial for tackling coding challenges effectively during interviews. The course is offered in C++, Python, Java, C#, and JavaScript, so you can pick the language you prefer.
Advanced topics: Once you have practiced interview questions of varying difficulty levels and mastered coding patterns, the next step involves diving into advanced topics like Dynamic Programming. Educative offers a comprehensive course, Grokking Dynamic Programming: A Deep Dive using Python, that teaches the advanced coding patterns that help to solve multiple types of dynamic programming problems. The course covers five coding patterns that help you understand multiple categories of dynamic problem questions and their respective solving patterns. As with other courses, it's available in multiple languages, including JavaScript, C++, Java, and Python.

Good luck with your preparation and next coding interview!

Frequently Asked Questions

What is a modified binary search?

A modified binary search adapts the standard binary search to solve specific problems, like finding an element’s first or last occurrence or searching in a rotated array.

What is a binary search?

Binary search quickly locates an element in a sorted list by repeatedly dividing the search range in half until the element is found or no range remains.

What are the different ways to implement binary search?

Binary search can be implemented in two main ways: iteratively and recursively. Both approaches use the same strategy of dividing the search space, but they differ in structure—one relies on loops, while the other uses function calls.

What is the main condition of binary search?

The main condition for binary search is that the array or list must be sorted. This allows the algorithm to efficiently divide the search space and eliminate half of the elements in each step.

What are the real-world uses of binary search?

Binary search is used in various real-world applications, such as searching large databases, finding elements in sorted collections, optimizing search algorithms in games, and solving problems like finding the square root or the shortest path in graphs.

What is the main condition of a modified binary search?

In modified binary search, the search space is adjusted by checking which half of the array is sorted and then determining whether the target could be in that sorted half before proceeding.

Join 2.5 million developers at

Explore the catalog

Free Resources

Learn in-demand tech skills in half the time

PRODUCTS

Mock Interview

New

Courses

Skill Paths

Projects

Assessments