↓Skip to main content
Algorithms

Binary Search Algorithm

8 mins
Table of Contents

You Might Also Like

A magnifying glass focusing on a sorted list of numbers, visually depicting the concept of searching through a collection efficiently, highlighting the precision and methodical nature of binary search.

Introduction #

The binary search algorithm is a powerful algorithm that can be used to solve a variety of problems. It is a great example of how a simple idea can lead to a very efficient algorithm. It is also a great example of how a simple idea can be implemented in different ways. The iterative and recursive versions of binary search are both correct and efficient. The choice between the two depends on the specific problem and the specific requirements.

A simple way to understand how a binary search work is to think of a physical dictionary. When you look up a word in a dictionary, you don’t start from the first page and read every single word until you find the word you are looking for. Instead, you open the dictionary in the middle and compare the word you see to the word you are looking for.

If the word you are looking for comes before the word you see, you discard the right half of the dictionary and repeat the process with the left half. If the word you are looking for comes after the word you see, you discard the left half of the dictionary and repeat the process with the right half. You continue this process until you find the word you are looking for or until there are no more words to look at.

The binary search requires the array to be sorted. If the array is not sorted, the binary search will not work.

The important thing to note here is that the dictionary is sorted. This is what allows you to discard half of the dictionary each time. If the dictionary was not sorted, you would have to look at every single word to find the word you are looking for, which is a linear search and is not efficient.

Consider that you have a sorted array of integers, you start at the middle index. If the middle element is the target, you return its index. If the middle element is smaller than the target, you ignore the left half of the array. The next middle element will be the right half of the array. Again, if the middle element is the target, you return its index. If the middle element is larger than the target, you ignore the right half of the array. The next middle element will be the left half of the array. And so on.

Consider the sorted array with indexes and values as shown below, and the target is 78.

index: 0,   1,   2,   3,   4,   5,   6,   7,   8,   9
value: 12,  23,  34,  45,  56,  67,  78,  89,  90,  100
1 2 2 3 3 4 4 5 S e 5 a 6 r * c h R 6 a 7 n g e 7 8 8 9 9 0 1 0 0

The range of the array is [0, 9]. The middle element is at index 4, which is 56. Since 56 is smaller than 78, we ignore the left half of the array, and find the next middle element in the right half of the array from the middle index, that is indexes 5 to 9.

index: 5,   6,   7,   8,   9
value: 67,  78 , 89 , 90 , 100
1 2 2 3 3 4 4 5 5 6 6 7 7 8 S e a r 8 c 9 h * R a n 9 g 0 e 1 0 0

The range of the array is now 5 to 9. The middle element is at index 7, which is 89. Since 89 is larger than 78, we ignore the right half of the array, and find the next middle element in the left half of the array, that is indexes 5 to 6.

index: 5,   6
value: 67,  78
1 2 2 3 3 4 4 5 5 6 S e 6 a 7 r * c h R 7 a 8 n g e 8 9 9 0 1 0 0

The range of the array is 5 to 6. The middle element is at index 5, which is 67. Since 67 is smaller than 78, we ignore the left half of the array, and find the next middle element in the right half of the array, which is index 6.

index: 6
value: 78
1 2 2 3 3 4 4 5 5 6 6 7 S e a r c 7 h 8 * R a n g e 8 9 9 0 1 0 0

The range of the array is 6 to 6. The middle element is at index 6, which is 78. Since 78 is the target, we return its index, which is 6.

This is the typical implementation of the binary search algorithm. It uses a while loop to find the target element. The loop continues until the left index is greater than the right index. If the target element is found, the index of the target element is returned. If the target element is not found, -1 is returned.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

public int search(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1;
}

line 2: The left index is initialized to 0.
line 3: The right index is initialized to the length of the array minus 1.
line 4: The while loop continues until the left index is greater than the right index.
line 5: The middle index is calculated
line 6: If the middle element is the target, the index of the middle element is returned.
line 9: If the middle element is smaller than the target, the left index is updated to mid + 1.
line 11: If the middle element is larger than the target, the right index is updated to mid - 1.
line 14: If the target element is not found, -1 is returned.\

Avoid Integer Overflow When Calculating the Middle Index #

You may have considered using (left + right) / 2 to find the middle index. However, this can cause an integer overflow. Instead, you can use left + (right - left) / 2 to find the middle index.

The overflow can happen when the sum of left and right is greater than the maximum positive integer value. This causes the sum to wrap around to a negative value. In the worst case, the sum of left and right will be equal to 2^31 - 1, which is the maximum positive value for a 32-bit signed integer data type. The sum will be negative if the next value is added to it. This causes an overflow and the value wraps around to a negative value.

An alternative implementation of the binary search algorithm is the recursive version. This version uses a helper method to find the target element. The helper method takes the array, the target element, and the left and right indexes as parameters. The helper method returns the index of the target element if it is found. If the target element is not found, -1 is returned.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

public int search(int[] nums, int target) {
    return search(nums, target, 0, nums.length - 1);
}

private int search(int[] nums, int target, int left, int right) {
    if (left > right) {
        return -1;
    }
    int mid = left + (right - left) / 2;
    if (nums[mid] == target) {
        return mid;
    } else if (nums[mid] < target) {
        return search(nums, target, mid + 1, right);
    } else {
        return search(nums, target, left, mid - 1);
    }
}

line 2: The recursive method is called with the array, the target element, and the left and right indexes.
line 4: The helper method takes the array, the target element, and the left and right indexes as parameters.
line 5: If the left index is greater than the right index, -1 is returned.
line 6: The middle index is calculated.
line 7: If the middle element is the target, the index of the middle element is returned.
line 8: If the middle element is smaller than the target, the helper method is called with the left index updated to mid + 1.
line 9: If the middle element is larger than the target, the helper method is called with the right index updated to mid - 1.

Conclusion #

The binary search is a powerful algorithm that can be used to solve a variety of problems. Learning this algorithm is a great way to improve your problem-solving skills. It is also a great way to learn about the importance of sorting and how it can be used to solve problems efficiently. The binary search algorithm is a great example of how a simple idea can lead to a very efficient algorithm. It is also a great example of how a simple idea can be implemented in different ways. The iterative and recursive versions of binary search are both correct and efficient. The choice between the two depends on the specific problem and the specific requirements.