Can you name algorithms based on the binary search method and explain their features?

Algorithms based on the binary search method use the principle of dividing a sorted array or search space in half to efficiently find the desired element or solve a problem. Here are some examples and their features:

• Classic binary search — finds an element in a sorted array in O(log n). Works only on sorted data.

• Finding the first or last occurrence of an element — a modification of binary search that allows finding the left or right boundary of a range of identical elements.

• Searching in an infinite or unknown-sized array — first expand the search boundaries exponentially, then apply binary search.

• Finding the root of an equation (bisection method) — used to find the root of a function on an interval where the function changes sign.

• Finding the optimal solution (binary search on the answer) — when you need to find the minimum or maximum value satisfying a condition checked by a predicate function.

Example of binary search in Java for finding an element in a sorted array:

public int binarySearch(int[] arr, int target) {
    int left = 0, right = arr.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1; // element not found
}