Binary Search

class Solution {
public:
    int findIndex(vector<int>& data, int goal) {
        int low = 0, high = int(data.size());
        
        while (low < high) {
            int middle = low + (high - low) / 2;
            if (data[middle] >= goal) {
                high = middle;
            } else {
                low = middle + 1;
            }
        }
        
        if (low < data.size() && data[low] == goal) {
            return low;
        } else {
            return -1;
        }
    }
};

The solution provided implements a binary search algorithm to find the index of a specified element (referred to as goal) in a sorted array data. The method findIndex within the Solution class details the steps of the binary search.

• Begin by initializing two pointers, low and high, which represent the boundaries of the segment of the array being searched. low starts at 0, and high is set to the total size of the array data.
• The algorithm enters a while loop, which continues as long as low is less than high.
  • Calculate the middle index of the current array segment using low + (high - low) / 2.
  • If the middle element is greater than or equal to goal, adjust the high pointer to the middle index to narrow the search towards the lower half.
  • Otherwise, adjust the low pointer to middle + 1 to shift the focus to the upper half of the segment.
• After exiting the loop, check if the element at the low index is the goal. If it is, return the low index.
• If the element is not found, return -1, indicating that the goal does not exist within the data array.

This approach efficiently narrows down the possible locations of goal by halving the search space with each iteration, which makes binary search very effective for large arrays. The solution ensures that if goal exists in data, its index will be returned; otherwise, -1 is returned, signaling its absence.

class Solution {
    public int findElement(int[] array, int value) {
        int start = 0, end = array.length;
        
        while (start < end) {
            int middle = start + (end - start) / 2;
            if (array[middle] >= value) {
                end = middle;
            } else {
                start = middle + 1;
            }
        }
        
        if (start < array.length && array[start] == value) {
            return start;
        } else {
            return -1;
        } 
    }
}

The provided Java solution implements a binary search algorithm that locates a specific integer value within a sorted array. The function, findElement, takes two parameters: an integer array array and the integer value to find. Here is a breakdown of how this binary search works:

• Initialize two pointers, start at 0 and end at the length of the array.
• Perform a loop where start is less than end:
  • Calculate middle as the average of start and end, adjusted to avoid overflow.
  • If the middle element is greater than or equal to value, adjust end to middle.
  • Otherwise, set start to middle + 1 to focus on the next segment of the array.
• After exiting the loop, check if start is less than the length of the array and if the element at start matches value:
  • If it matches, return the index start.
  • If no match is found, return -1 indicating that the value does not exist in the array.

This method ensures an efficient search with a time complexity of O(log n), leveraging the dividing approach of binary search. This algorithm is particularly effective for large, sorted arrays where a linear search would be too slow.

class Solution:
    def binary_search(self, numbers: List[int], search_value: int) -> int:
        low = 0
        high = len(numbers)

        while low < high:
            mid_point = (low + high) // 2
            if numbers[mid_point] >= search_value:
                high = mid_point
            else:
                low = mid_point + 1
        
        if low < len(numbers) and numbers[low] == search_value:
            return low
        else:
            return -1

The provided Python solution defines a method for performing a binary search on a sorted array of integers to find a specific target value. Employ the following solution steps for an effective binary search:

1. Initialize the variables low to 0 and high to the length of the input list, numbers.
2. Initiate a while loop that continues as long as low is less than high.
3. Inside the loop:
   • Calculate the midpoint mid_point as the average of low and high.
   • If the element at mid_point in numbers is greater than or equal to search_value, adjust high to mid_point.
   • If not, increment low by one (mid_point + 1).
4. After exiting the loop:
   • Check if low is within the bounds of numbers and if numbers[low] equals search_value.
   • If it matches, return the index low, indicating the position where search_value is found.
   • If not, return -1 to indicate that search_value is not in the list.

The method returns the index of search_value if it exists within numbers, otherwise, it returns -1. This efficient way to search in sorted arrays reduces time complexity significantly compared to linear search.