二分查找

为了解决这个问题，我们需要编写一个使用二分查找法的函数来在一个有序整数数组中查询某个元素的位置。如果找到该元素，则返回其索引；如果未找到，则返回-1。

方法思路

二分查找是一种高效算法，适用于有序数组。其基本思想是将目标值与数组中间元素进行比较，逐步缩小搜索范围。具体步骤如下：

1. 初始化两个指针 left 和 right，分别指向数组的开始和末尾。
2. 计算中间索引 mid，并将数组的中间元素与目标值进行比较。
3. 如果中间元素等于目标值，则返回中间索引；如果中间元素小于目标值，则将搜索范围调整为数组的右半部分；否则，调整为左半部分。
4. 重复上述步骤，直到找到目标值或确定其不存在于数组中。

这种方法的时间复杂度为 O(log n)，效率很高。

解决代码

public class BinarySearch {
    public static int binarySearch(int[] array, int target) {
        int left = 0;
        int right = array.length - 1;
​
        while (left <= right) {
            int mid = left + (right - left) / 2; // 避免整数溢出
            if (array[mid] == target) {
                return mid;
            } else if (array[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
​
        return -1; // 如果没有找到目标值，返回-1
    }
​
    public static void main(String[] args) {
        int[] array = {1, 3, 5, 7, 9};
        System.out.println(binarySearch(array, 5));   // 输出: 2
        System.out.println(binarySearch(array, 6));   // 输出: -1
    }
}

代码解释

• 函数 binarySearch：接受一个有序整数数组和目标值作为参数。
• 初始化指针：left 和 right 分别指向数组的开始和末尾。
• 循环比较：在每次循环中计算中间索引 mid，并将数组中间元素与目标值进行比较。根据比较结果调整搜索范围。
• 返回结果：如果找到目标值，返回其索引；否则，循环结束后返回-1。

这个方法确保了在有序数组中高效查找元素的位置，避免了不必要的比较操作，提高了算法效率。