# 1. Introduction

Binary search is an efficient algorithm for finding an item from a sorted list of items. It works by repeatedly dividing in half the portion of the list that could contain the item, until you've narrowed the possibilities down to just one.

# 2. Implementation Steps

2. If the middle item matches the target value, return its index.

3. If the target value is less than the middle item, continue the search in the lower half of the list.

4. If the target value is greater than the middle item, continue the search in the upper half of the list.

5. Repeat steps 1-4 until the target value is found or the search interval is empty.

# 3. Implementation in Java

``````public class BinarySearch {
// Binary Search method
public static int binarySearch(int arr[], int l, int r, int x) {
while (l <= r) {
int mid = l + (r - l) / 2;
// Check if x is present at mid
if (arr[mid] == x) {
return mid;
}
// If x is greater, ignore left half
if (arr[mid] < x) {
l = mid + 1;
}
// If x is smaller, ignore right half
else {
r = mid - 1;
}
}
return -1;
}
public static void main(String[] args) {
int arr[] = { 1, 3, 5, 7, 9, 11, 13, 15 };
int x = 9;
int result = binarySearch(arr, 0, arr.length - 1, x);
if (result == -1) {
System.out.println("Element not present in the array");
} else {
System.out.println("Element is present at index: " + result);
}
}
}
``````

### Output:

```Element is present at index: 4
```

### Explanation:

1. Begin by examining the middle item of the sorted array.

2. If this item matches the target value, then the position of this item in the array is returned.

3. If the target value is less than this item, search for the item in the lower half of the array.

4. If the target value is greater than this item, search for the item in the upper half of the array.

5. Continue the process until the target item is found or the search interval is empty. If the interval becomes empty, return -1 to indicate the target value is not present in the array.