位运算
除法在计算机中效率很低,一般改用 >> x
,意思是二进制数的每个位右移 x 位。从十进制的角度看, x 是以 2 为底的指数,这个指数就是除数。文章来源:https://www.toymoban.com/news/detail-813971.html
//等价式
mid = (low + high) / 2;
mid = low + high >> 2; //效率提高
mid = low + (high - low >> 2); //防止(low + high)溢出
在 Java 中,位运算符 >>
的优先级低于加法运算符 +
,所以需要使用括号来保证正确的优先级文章来源地址https://www.toymoban.com/news/detail-813971.html
用递归实现二分查找
/**
* @param arr 升序数组
*/
public static int binarySearch(int[] arr, int low, int high, int target)
{
if(low > high)
return -1; //没有找到返回-1
int mid = low + (high - low >> 1);
if(arr[mid] == target)
return mid; //返回目标值的位置
else if(arr[mid] < target)
return binarySearch(arr,mid + 1, high, target); //向右寻找
else
return binarySearch(arr, low, mid - 1, target); //向左寻找
}
有重复元素的二分查找
迭代实现
public static int binarySearch(int[] arr, int target)
{
int low = 0;
int high = arr.length - 1;
// 使用二分查找法查找target
while (low <= high)
{
int mid = low + (high - low >> 1);
// 如果中间元素等于target,则返回中间元素索引
if (arr[mid] == target)
{
// 如果中间元素不是第一个元素,则继续向前查找
while (mid != 0 && arr[mid] == target)
mid--;
// 如果中间元素是第一个元素,则返回0
if (mid == 0)
return 0;
else
return mid + 1;
}
// 如果中间元素小于target,则将low移动到mid+1
else if (arr[mid] < target)
low = mid + 1;
// 如果中间元素大于target,则将high移动到mid-1
else
high = mid - 1;
}
// 如果查找结束没有找到target,则返回-1
return -1;
}
到了这里,关于逢试必考的二分查找(算法村第九关青铜挑战)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!