Tag: Java Operators

Introduction

Binary search is a search algorithm that works on sorted data. It operates by repeatedly dividing the search interval in half until the target value is found or the interval is empty. It’s a very efficient algorithm, with a runtime complexity of O(log n), where n is the number of elements in the array.

In this article, we’ll walk through how to implement binary search in Java to search for an integer in a sorted array.

Implementation

Let’s start by writing a method that performs a binary search. The method takes two arguments: an array of integers nums and an integer target that we’re searching for. The method returns the index of the target if it exists in the array, or -1 if it doesn’t.

public static int binarySearch(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;
}

Here’s how the method works:

• We start by setting left to the first index of the array, and right to the last index of the array.
• We use a while loop to keep searching until the search interval is empty (left is greater than right), or we’ve found the target value.
• In each iteration of the loop, we compute the midpoint of the search interval using the formula mid = left + (right - left) / 2. This avoids integer overflow errors that can occur if we use the simpler formula (left + right) / 2.
• If the value at nums[mid] is equal to the target, we’ve found it, so we return mid.
• If the value at nums[mid] is less than the target, we need to search the right half of the search interval, so we update left = mid + 1.
• If the value at nums[mid] is greater than the target, we need to search the left half of the search interval, so we update right = mid - 1.

Example

Let’s look at an example of how to use the binarySearch method. Suppose we have the following array of integers:

int[] nums = {1, 3, 5, 7, 9};

We want to search for the value 5 in the array. We can call the binarySearch method like this:

int index = binarySearch(nums, 5);

The index variable will contain the value 2, which is the index of the value 5 in the array.

Conclusion

Binary search is a very efficient algorithm for searching sorted data. In this article, we’ve seen how to implement binary search in Java to search for an integer in a sorted array. We used a while loop to repeatedly divide the search interval in half, and we updated the search interval based on whether the target value was greater than or less than the midpoint value. By using this algorithm, we can search a large array in logarithmic time, which is much faster than linear search.