A binary search algorithm assumes the input array to be sorted and finds the
position of a specified value within that array. In each step, the algorithm compares the search value with value at the middle element of the array. If it match, then a matching
element has been found so its index, or position, is returned. Otherwise, if value is less than the middle element's value, then the algorithm
repeats its action on the sub-array to the left of the middle element or, if
the input key is greater, on the sub-array to the right.

Worst case performance: O(log n)

Best case performance: O(1)

Assumption: Input array is sorted

Assumption: Input array is sorted

```
public class BinarySearch {
public static void main(String[] args) {
BinarySearch binarySearch = new BinarySearch();
int[] inputArray = { 1, 3, 6, 8, 12, 23, 29, 31, 46, 59, 77, 81, 95 };
int searchInt = 3;
System.out.println("Position for " + searchInt + " is "
+ binarySearch.binarySearch(inputArray, searchInt));
}
public int binarySearch(final int[] inputArr, final int key) {
int startIndex = 0;
int endIndex = inputArr.length - 1;
while (startIndex <= endIndex) {
// Search for key at mid index, if found return the index.
int mid = (startIndex + endIndex) / 2;
if (key == inputArr[mid]) {
return mid;
}
// if key is not found, update the start and end index
if (key < inputArr[mid]) {
endIndex = mid - 1;
} else {
startIndex = mid + 1;
}
}
return -1;
}
}
```

Output:

```
Position for 3 is 1
```

Hope you liked the above post, connect at +Java Territory to stay updated with latest articles.

## 0 comments:

## Post a Comment