二分查找

xiaoxiao2021-02-28  8

二分查找的思路就是:首先传入的数组要有序,然后每次都与中间的数据做比较,再判断是找到了要找的数据,还是找得大了还是找得小了,然后再决定接下去比较的范围

/** * * @param arr从小到大的有序的数组 * @param target目标数字 * @return目标数字所在的下标 */ public static int BinarySearch(int[] arr,int target){ int left = 0; int right = arr.length - 1; while(left <= right){ //循环退出的条件 int temp = left + (right - left)/2; //可以防止数据越界 if(target == arr[temp]){ //每次都与中间的数值做比较 return temp+1; }else if(target > arr[temp]){ left = temp + 1; }else{ right = temp - 1; } } return -1; }

也可以采用递归的方式来查询

private static int i = -1; /** * * @param arr从小到大的有序数组 * @param left起始位置 * @param right终止位置 * @param target目标数字 * @return返回目标数字的下标 */ public static int BinarySearch_2(int[] arr,int left,int right,int target){ if(left<=right){ int temp = left + (right - left)/2; if(target == arr[temp]){ i = temp; }else{ if(target > arr[temp]){ left = temp + 1; }else{ right = temp - 1; } BinarySearch_2(arr,left,right,target); } } return i; }
转载请注明原文地址: https://www.6miu.com/read-2400301.html

最新回复(0)