二分查找（Binary Search）

二分查找是一种在有序数组中快速查找目标元素的高效算法，时间复杂度为 O(log n)，比线性查找的 O(n) 快得多。

基本思想

有序前提：数组必须是有序的（升序或降序）
分而治之：每次比较都将搜索范围缩小一半
终止条件：找到目标值或搜索范围为空

基本实现（迭代版）

public int binarySearch(int[] nums, int target) {int left = 0;int right = nums.length - 1;while (left <= right) {int mid = left + (right - left) / 2; // 防止溢出if (nums[mid] == target) {return mid; // 找到目标} else if (nums[mid] < target) {left = mid + 1; // 目标在右半部分} else {right = mid - 1; // 目标在左半部分}}return -1; // 未找到
}

递归实现

public int binarySearchRecursive(int[] nums, int target, int left, int right) {if (left > right) {return -1;}int mid = left + (right - left) / 2;if (nums[mid] == target) {return mid;} else if (nums[mid] < target) {return binarySearchRecursive(nums, target, mid + 1, right);} else {return binarySearchRecursive(nums, target, left, mid - 1);}
}