dede 网站打开慢,萧山建设局网站,哪里网站开发好,网站页面做多宽介绍
二分查找#xff08;Binary Search#xff09;是一种在有序数组中查找特定元素的搜索算法。其基本思想是将目标值与数组中间的元素进行比较#xff1a;
如果目标值等于中间元素#xff0c;则查找成功。如果目标值小于中间元素#xff0c;则在数组左半部分继续进行二…介绍
二分查找Binary Search是一种在有序数组中查找特定元素的搜索算法。其基本思想是将目标值与数组中间的元素进行比较
如果目标值等于中间元素则查找成功。如果目标值小于中间元素则在数组左半部分继续进行二分查找。如果目标值大于中间元素则在数组右半部分继续进行二分查找。
这个过程将不断重复直到找到目标值或搜索范围为空为止。
实现步骤
下面是二分查找算法的一般步骤
初始化两个指针一个指向数组的起始位置low另一个指向数组的结束位置high。计算中间位置midmid⌊(lowhigh)/2⌋mid⌊(lowhigh)/2⌋比较中间元素与目标值 如果中间元素等于目标值返回中间位置。如果中间元素大于目标值将high更新为mid - 1。如果中间元素小于目标值将low更新为mid 1。重复步骤2和3直到找到目标值或low大于high为止。
如果最终low大于high表示目标值不在数组中可以返回一个表示未找到的值比如-1。
二分查找的时间复杂度是O(log n)其中n是数组的大小。这使得它在处理大型数据集时非常高效。然而二分查找要求数组必须是有序的这是它的一个限制条件。
代码实现
public class BinarySearch {public static void main(String[] args) {// 初始化一个有序数组int[] arr {1, 8, 10, 34, 44, 46, 56, 59, 61, 63, 66, 68, 69, 70, 89, 1000, 1234};// 使用递归版本查找目标值89在数组中的索引int index binarySearch(arr, 0, arr.length - 1, 89);// 使用循环版本查找目标值89在数组中的索引int index1 binarySearch(arr, 89);// 打印两个版本的查找结果System.out.println(index index1);}// 递归版本的二分查找算法private static int binarySearch(int[] arr, int left, int right, int target) {// 基本情况如果left大于right说明target不在数组中返回-1if(left right) {return -1;}// 计算中间索引int mid (left right) / 2;// 如果中间元素等于目标值返回中间索引if(arr[mid] target) {return mid;} else if(arr[mid] target) {// 如果中间元素大于目标值在左半部分递归调用二分查找return binarySearch(arr, left, mid - 1, target);} else {// 如果中间元素小于目标值在右半部分递归调用二分查找return binarySearch(arr, mid 1, right, target);}}// 循环版本的二分查找算法private static int binarySearch(int[] arr, int target) {// 初始化左右指针int left 0;int right arr.length - 1;// 当left小于等于right时继续循环while(left right) {// 计算中间索引int mid (left right) / 2;// 如果中间元素等于目标值返回中间索引if(arr[mid] target) {return mid;} else if(arr[mid] target) {// 如果中间元素大于目标值更新right为mid-1right mid - 1;} else {// 如果中间元素小于目标值更新left为mid1left mid 1;}}// 如果没有找到目标值返回-1return -1;}
}
测试结果 产生问题
在二分查找算法中计算中间索引 mid 的表达式 int mid (left right) / 2; 可能会在某些情况下导致问题。具体来说如果 left 和 right 是非常大的整数那么它们的和可能会超出 int 类型所能表示的范围导致整数溢出。
整数溢出会导致 mid 的值不正确这可能会使二分查找算法无法正确执行甚至进入无限循环。
举例说明 解决问题 使用位运算 使用位运算来避免溢出因为位运算是按位进行的不会导致溢出。计算 mid 的表达式如下
midleft (( right − left ) 1 )
这里 是右移位运算符它将 right - left 的二进制表示向右移动一位相当于除以2。
使用这些方法可以确保在执行二分查找时 mid 的值是正确的从而避免因整数溢出导致的问题
修改代码 // 递归版本private static int binarySearch(int[] arr, int left, int right, int target) {if(left right) {return -1;}// int mid (left right)/2;int mid left ((right - left) 1);if(arr[mid] target) {return mid;} else if(arr[mid] target) {return binarySearch(arr, left, mid - 1, target);} else {return binarySearch(arr, mid 1, right, target);}}// 循环版本private static int binarySearch(int[] arr, int target) {int left 0;int right arr.length - 1;while(left right) {//int mid (left right)/2;int mid left ((right - left) 1);if(arr[mid] target) {return mid;} else if(arr[mid] target) {right mid - 1;} else {left mid 1;}}return -1;}测试结果
