What is the best approach to find the mid index in binary search?

The binary search employs two integer variables to indicate the search space; one records the starting index of the search space, and the other variable records the ending index of the search space. Initially, the search space is the complete array, as shown in the following illustration. The start index of the search space is 0, and the end index is one less than the array’s length. We find the mid (middle element index) of the search space so that we can compare the searched number with the middle element in the search space. This helps reduce the search space to either the left part (the end index moves to the index one less than the mid) or the right part (the start index moves to the index one greater than the mid) of the middle element.

Problem

This method seems to work because we usually consider small-size arrays. Now assume we have a very large array of size greater than half of the maximum INT value (2147483647). If each time the search space reduces to the right part of the middle element, the start and the end pointer reach the last indices in the array, which are very large, greater than half of the maximum INT value (2147483647). Adding two index values (start and end) that are greater than half of the maximum INT value (2147483647) will exceed the maximum INT value. As a result, the sum (start + end) overflows to a negative value and will remain negative after dividing by 2. The negative index couldn’t be found in the array, and we'll get an index out of bound error.

#include <climits>
#include <iostream>
#include <cmath>
using namespace std;
int main() {
  cout << "Minimum int value(INT_MIN)= " << INT_MIN << endl;
  cout << "Maximum int value(INT_MAX)= " << INT_MAX << endl;
  cout << "Half of the maximum int value = INT_MAX/2 = " << INT_MAX/2 << endl;
  int sizeofArr = (ceil(INT_MAX/2)) + 10; // Making array size greater than half of the maximum int value
  cout << "Size of array (Ten greater than half of the Maximum int value)= " << sizeofArr << endl << endl;
  
  int start=1073741830; //The start index reached the 1073741830'th index of the array
  int end=sizeofArr-1; //The end index is at the last index of the array
  cout << "Assume the 'start' index has reached 1073741830'th index of the array." << endl;
  cout << "Assume the 'end' is at the last index of the array = sizeofArr-1 = " << sizeofArr-1 << endl << endl;
  
  int mid = (start + end)/2; //Finding middle element index using the greedy approach
  cout << "Middle element index found with greedy approach((start + end)/2): "<< mid << endl; // Greedy approach gives negative mid index, which is not in the array indices range, so if we access the array element at this mid index, then we will get an index out of bound error
  
  mid = start + ((end - start) / 2); //Finding middle element index using the best approach
  cout << "Middle element index found with best approach(start + ((end - start) / 2)): "<< mid << endl; // The best approach gives a positive index value unless the size of the array exceeds the maximum value of the INT
  
  return 0;
}

What is the best approach to find the mid index in binary search?

The greedy approach

Problem

The best approach

Code example

Output