二分查找是一种在有序数组中查找特定元素的高效算法。其基本思路是通过逐步缩小查找范围来找到目标元素。每次将查找范围的中间元素与目标元素进行比较，根据比较结果决定继续查找左半部分还是右半部分。

二分查找的实现思路：

1. 输入：一个有序数组 arr 和一个目标值 target。
2. 初始化：设置两个指针，left 和 right，分别指向数组的左右两端（即 left = 0，right = arr.length - 1）。
3. 循环查找：
   • 计算中间位置 mid = left + (right - left) / 2。
   • 如果 arr[mid] == target，则找到了目标值，返回 mid（即元素的索引）。
   • 如果 arr[mid] < target，说明目标值可能在右半部分，将 left 移动到 mid + 1。
   • 如果 arr[mid] > target，说明目标值可能在左半部分，将 right 移动到 mid - 1。
4. 退出条件：如果 left 超过了 right，说明数组中没有目标元素，返回 -1。

时间复杂度与空间复杂度分析：

• 时间复杂度：O(log n)，每次查找将问题的规模减少一半，因此时间复杂度为对数级别。
• 空间复杂度：O(1)，使用常数空间，只需要几个额外的变量（left、right 和 mid）来存储指针，没有使用额外的空间。

Java 完整代码实现：

public class BinarySearch {

    // 二分查找函数
    public static int binarySearch(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;

        // 进行二分查找
        while (left <= right) {
            // 计算中间索引
            int mid = left + (right - left) / 2;

            // 检查中间元素是否为目标值
            if (arr[mid] == target) {
                return mid; // 找到目标，返回其索引
            }

            // 如果目标值大于中间元素，则调整搜索范围为右半部分
            if (arr[mid] < target) {
                left = mid + 1;
            }
            // 如果目标值小于中间元素，则调整搜索范围为左半部分
            else {
                right = mid - 1;
            }
        }

        // 目标值不存在于数组中，返回 -1
        return -1;
    }

    // 主函数，用于测试
    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
        int target = 7;
        
        // 调用二分查找方法
        int result = binarySearch(arr, target);
        
        if (result != -1) {
            System.out.println("目标元素 " + target + " 在数组中的索引是: " + result);
        } else {
            System.out.println("目标元素 " + target + " 不在数组中");
        }
    }
}

代码解释：

• binarySearch 方法：接收一个有序整数数组 arr 和一个目标值 target。通过不断调整左右指针，最终找到目标值并返回其索引。如果没有找到目标元素，则返回 -1。
• main 方法：用于测试 binarySearch 方法。数组 arr 是已排序的，target 是我们要查找的目标值。

样例输出：

目标元素 7 在数组中的索引是: 3