# Binary Search in Java

28

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:

## 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;
}
}

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 {
}
}
}
``````

### 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.

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