查找算法-二分查找（折半查找）
二分查找（Binary Search）算法是一种在有序数组中查找特定元素的搜索算法。它通过不断将数组分成两半，判断目标值可能存在的区间，从而缩小搜索范围，直到找到目标值或搜索范围为空。二分查找的时间复杂度为O(log n)，其中n是数组的长度。
以下是二分查找算法的关键知识点和Java实现示例：
知识点
- 前提条件：数组必须是有序的。
- 基本思想：通过比较数组中间元素与目标值的大小，判断目标值可能存在的区间，然后继续在可能存在目标值的区间内查找，直到找到目标值或区间为空。
- 边界处理：在每次迭代中，需要正确更新查找区间的边界（即左边界
left和右边界right）。 - 循环条件：循环继续的条件是左边界小于等于右边界，即
left <= right。 - 返回结果：如果找到目标值，则返回其索引；如果遍历完整个可能区间仍未找到目标值，则返回特定值（如-1）表示未找到。
Java实现示例
public class BinarySearch { /** * 二分查找算法 * @param arr 有序数组 * @param target 要查找的目标值 * @return 目标值在数组中的索引，如果未找到则返回-1 */ 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; // 找到目标值，返回其索引 } else if (arr[mid] < target) { left = mid + 1; // 目标值在右半部分，更新左边界 } else { right = mid - 1; // 目标值在左半部分，更新右边界 } } return -1; // 未找到目标值，返回-1 } public static void main(String[] args) { int[] arr = {-1, 0, 3, 5, 9, 12}; int target = 9; int result = binarySearch(arr, target); if (result != -1) { System.out.println("找到目标值，位置为：" + result); } else { System.out.println("未找到目标值"); } }
}在这个示例中，binarySearch方法实现了二分查找算法。它接受一个有序数组arr和一个目标值target作为参数，并返回目标值在数组中的索引。如果未找到目标值，则返回-1。main方法创建了一个有序数组和一个目标值，并调用了binarySearch方法来查找目标值，最后打印出查找结果。