binary search return index c++

Binary Search in C++

Binary search is an efficient algorithm used to find a specific element in a sorted list or array. It works by repeatedly dividing the search space in half until the target element is found.

Here's the step-by-step explanation of the binary search algorithm in C++:

Initialization: Start by defining the search space, which includes the lower and upper bounds of the array or list. These bounds are usually represented as indices, such as start and end, where start is the index of the first element and end is the index of the last element.
Finding the middle: Calculate the mid index as the average of the start and end indices. This will give us the index of the middle element in the current search space.
Comparison: Compare the target element with the middle element of the search space.

a. If the target element is equal to the middle element, we have found the desired element and can return the index.

b. If the target element is less than the middle element, we update the end index to be mid - 1 and repeat the process from step 2 with the updated search space.

c. If the target element is greater than the middle element, we update the start index to be mid + 1 and repeat the process from step 2 with the updated search space.

Repeat: Repeat steps 2 and 3 until the target element is found or the search space is empty (start becomes greater than end).
Element not found: If the search space becomes empty and the target element is not found, return a value indicating that the element was not present in the array or list.
Element found: If the target element is found, return the index of the element in the array or list.

This algorithm has a time complexity of O(log n), where n is the number of elements in the array or list. It efficiently reduces the search space by half in each iteration, making it suitable for large datasets.

Here's an example implementation of the binary search algorithm in C++:

int binarySearch(int arr[], int target, int start, int end) {
    while (start <= end) {
        int mid = start + (end - start) / 2;

        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            start = mid + 1;
        } else {
            end = mid - 1;
        }
    }

    return -1; // Element not found
}

This implementation takes an array arr[] and the target element target, along with the initial start and end indices of the search space. It returns the index of the target element if found, or -1 if the element is not present.