黄山网站建设推荐,外贸网站模板有什么用,太原做网站的公司哪家好,wordpress大前端d8主题二分法查找索引值 二分法查找算法步骤#xff1a;(前提#xff1a;查询数组为一组有序数)1、定义低位和高位指针low#xff0c;high#xff1b;2、通过判断low和high的所指的数值中间值mid来判断关键值是在高位段还是低位段。例题解析#xff1a; 查找5的索引值 sum {1,2…二分法查找索引值 二分法查找算法步骤(前提查询数组为一组有序数)1、定义低位和高位指针lowhigh 2、通过判断low和high的所指的数值中间值mid来判断关键值是在高位段还是低位段。 例题解析 查找5的索引值 sum {1,2,3,4,5,6,7,8,9,10} 代码的非递归实现:
/*** 非递归方法* 时间复杂度T(n)O(n)* 空间复杂度S(n)O(1)* return*/public static int search(int [] arr,int key){//定义low与high的值int low0;int higharr.length-1;//利用折半查找查找索引值while(low high){//确定mid的值int mid(lowhigh)1;if(keyarr[mid])return mid;else if(keyarr[mid])highmid-1;elselowmid1;}return -1;}二分查找易错的地方 循环退出的条件 注意是low high,而不是lowhigh. mid的取值 如果写成 mid (lowhigh)/2是有问题,如果low和high比较大,两者的和可能会溢出改进的方案low(high-low)/2,但是计算机位运算比除法快,故可改成low((high-low)1)
代码的递归实现
/*** 递归方法* 时间复杂度T(n)O(log2(n))* 空间复杂度S(n)O(log2(n))*/public static int search1(int arr[],int key){//定义low与high的值int low0;int higharr.length-1;return sreach(arr,key,low,high);}public static int sreach(int arr[],int key,int low,int high){int mid(lowhigh)/2;if(keyarr[mid])return mid;if(lowhigh)return -1;else if(keyarr[mid])return sreach(arr,key,low,mid-1);elsereturn sreach(arr,key,mid1,high);}
