Binary Search in Java

By
Shivam Gupta
-
44
Binary Search in Java
Advertisement

Binary search is a powerful algorithm used to efficiently find a target value in a sorted array. In this blog post, we’ll delve into the details of implementing binary search in Java for a sorted array. We’ll provide a Java program with detailed explanations, examples, and code snippets to help you understand the logic behind this algorithm.

Understanding Binary Search

Binary search works by repeatedly dividing the search interval in half. It compares the target value to the middle element of the array. If the target is equal to the middle element, the search is successful. If the target is less than the middle element, the search continues in the lower half of the array. Similarly, if the target is greater than the middle element, the search continues in the upper half. This process continues until the target is found or the search interval becomes empty.

How Does Binary Search Work?

Here’s a step-by-step explanation:

  1. Initialize Pointers: Start with two pointers, left and right, which represent the range of elements to search within. left points to the first element of the array, and right points to the last element.
  2. Calculate Midpoint: Calculate the midpoint of the array using the formula mid = left + (right - left) / 2. This ensures we get the middle index even for large arrays, avoiding integer overflow.
  3. Compare Target with Midpoint:
  • If the target value is equal to the value at the midpoint, we’ve found the target, and we return the index of the midpoint.
  • If the target is less than the value at the midpoint, we update right = mid - 1, narrowing the search to the left half of the array.
  • If the target is greater than the value at the midpoint, we update left = mid + 1, narrowing the search to the right half of the array.

4. Repeat or Exit:

  • We continue this process, dividing the array in half each time until left is greater than right. This means the target is not in the array, and we return -1 to indicate that the target is not found.

You have to sort your Array before searching the element using Binary search. You can use any one of the below Sorting techniques to sort the array:

  1. Insertion Sort
  2. Quick Sort
  3. Merge Sort
  4. Bubble Sort
  5. Selection Sort

Java Program for Binary Search

Java Program – Binary Search
public class BinarySearch {

    public static int binarySearch(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            // Check if target is present at mid
            if (arr[mid] == target) {
                return mid;
            }

            // If target is greater, ignore left half
            if (arr[mid] < target) {
                left = mid + 1;
            }

            // If target is smaller, ignore right half
            else {
                right = mid - 1;
            }
        }

        // Target not found
        return -1;
    }

    public static void main(String[] args) {
        int[] sortedArray = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
        int target = 23;

        int result = binarySearch(sortedArray, target);
        if (result != -1) {
            System.out.println("Element found at index " + result);
        } else {
            System.out.println("Element not found");
        }
    }
}

Explanation of the Java Program

  • We define a binarySearch method that takes in a sorted array arr and a target value target.
  • We initialize two pointers left and right to the start and end of the array, respectively.
  • In the while loop, we calculate the mid index using the formula mid = left + (right - left) / 2.
  • We check if the target is equal to the value at the mid index. If so, we return the mid index.
  • If the target is greater than the mid value, we update left to mid + 1 to search in the right half.
  • If the target is smaller than the mid value, we update right to mid - 1 to search in the left half.
  • We continue this process until left is greater than right, indicating that the target is not found.

Example of Binary Search

Let’s say we have the sorted array: [2, 5, 8, 12, 16, 23, 38, 56, 72, 91] and we want to find the index of the target value 23.

Initial State:

  • left = 0 (index of first element)
  • right = 9 (index of last element)
  • mid = 4 (index of middle element)
  • arr[mid] = 16

First Iteration:

  • Since 23 is greater than 16, we update left = mid + 1:
    • left = 5
    • right = 9
    • mid = 7
    • arr[mid] = 56

Second Iteration:

  • Since 23 is less than 56, we update right = mid - 1:
    • left = 5
    • right = 6
    • mid = 5
    • arr[mid] = 23
  • We found the target 23 at index 5!

Complexity

Binary search is incredibly efficient for searching in sorted arrays. It has a time complexity of O(log n), which means it can find the target in logarithmic time, even for large arrays.

ScenarioTime ComplexitySpace Complexity
Best CaseO(1)O(1)
Average CaseO(log n)O(1)
Worst CaseO(log n)O(1)

In the best case, Binary Search finds the target element at the middle of the array in the first comparison, resulting in constant time complexity O(1). The space complexity remains constant O(1) as well.

For the average and worst cases, Binary Search has a logarithmic time complexity O(log n), where n is the number of elements in the array. It divides the search space in half with each comparison, making the search efficient for large datasets. The space complexity remains constant O(1) in these cases too, as it only requires a few extra variables for indices and calculations.

Conclusion

Binary search is a powerful and efficient algorithm for finding a target value in a sorted array. It’s a foundational concept in computer science and programming, and understanding it will serve you well as you continue your programming journey.

Feel free to try implementing binary search in your favorite programming language, and experiment with different arrays and target values to get a feel for how it works. Happy learning!

Latest Posts

RELATED ARTICLESMORE FROM AUTHOR