This problem requires searching in a sorted array. Think about algorithms that can take advantage of the sorted property to search more efficiently than linear search.
Binary search uses a divide-and-conquer approach. In each step, you eliminate half of the remaining search space.
Start by looking at the middle element of the array. Compare it with your target value to decide which half of the array to search next.
Use two pointers: left and right to track the current search boundaries. Update these pointers based on your comparison with the middle element.
Continue searching while left <= right. When this condition becomes false, the element is not in the array.
When calculating the middle index, use left + (right - left) / 2 instead of (left + right) / 2 to avoid potential integer overflow.
Return the index if the element is found, or -1 if the element is not in the array.