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:

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

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

Scenario | Time Complexity | Space Complexity |
---|---|---|

Best Case | O(1) | O(1) |

Average Case | O(log n) | O(1) |

Worst Case | O(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**

- Merging Two Sorted Arrays in JavaTitle: Merging Two Sorted Arrays in Java Merging two sorted arrays into a single array is a common operation in… Read more: Merging Two Sorted Arrays in Java
- Frequency of Elements in an ArrayTitle: Frequency of Elements in an Array Using Java Counting the frequency of elements in an array is a fundamental… Read more: Frequency of Elements in an Array
- Calculate the sum of diagonals in a matrixTitle: Calculate the sum of diagonals in a matrix In this blog post, we’ll delve into the world of matrices… Read more: Calculate the sum of diagonals in a matrix
- Binary Search in JavaBinary search is a powerful algorithm used to efficiently find a target value in a sorted array. In this blog… Read more: Binary Search in Java
- Removing Duplicate Elements in Array using JavaRemoving Duplicate Elements in Array using Java Arrays are fundamental in Java, but duplicate elements can clutter your data. In… Read more: Removing Duplicate Elements in Array using Java
- Transpose a 2D Array in JavaTitle: Transpose a 2D Array in Java In Java, transposing a 2D array involves converting its rows into columns and… Read more: Transpose a 2D Array in Java