二分法查找java实现

二分法（Binary Search）是一种查找算法，其思想是将查找区域分为两个部分，如果待查的数据存在于其中一部分，则继续在该部分中查找，否则在另一部分中查找。这种查找算法的时间复杂度为O(log n)，比线性查找更加高效。

在Java中实现二分法可以使用递归或者循环，下面分别介绍。

递归实现

递归实现二分法需要两个参数，一个是待查找的数组，另一个是待查找的数字。设置两个变量，left和right，分别表示数组的左侧和右侧位置。递归的过程与二分法类似，每次找到中间位置的数字，如果该数字等于待查找的数字，则返回中间位置，否则判断待查找的数字在左侧还是右侧。如果在左侧，则对左侧进行递归查找，反之对右侧进行递归查找。递归的终止条件是待查找数组为空或left>right。

以下是使用递归实现二分法的Java代码实现：

```

public static int binarySearchRec(int[] arr, int target, int left, int right) {

if (left <= right) {

int mid = left + (right - left) / 2;

if (arr[mid] == target) {

return mid;

} else if (arr[mid] > target) {

return binarySearchRec(arr, target, left, mid - 1);

} else {

return binarySearchRec(arr, target, mid + 1, right);

}

}

return -1;

}

```

循环实现

循环实现二分法的代码逻辑与递归实现相似，但是与递归实现不同的是，循环实现完全利用了循环语句的特性，没有使用递归函数来实现查找过程。需要设置三个变量，left、right和mid，以及一个循环条件。每次判断中间位置的数字，如果和待查找数字相等，则返回中间位置，否则判断待查找数字在左侧还是右侧，并改变left和right的值以达到缩小查找区间的目的。循环条件为left<=right。

以下是使用循环实现二分法的Java代码实现：

```

public static int binarySearch(int[] arr, int target) {

int left = 0, right = arr.length - 1;

while (left <= right) {

int mid = left + (right - left) / 2;

if (arr[mid] == target) {

return mid;

} else if (arr[mid] > target) {

right = mid - 1;

} else {

left = mid + 1;

}

}

return -1;

}

```

注意点

在实现二分法时要注意数组越界的问题。例如，在递归实现中，每次查找时要判断left是否小于等于right；在循环实现中，mid要使用(left+right)/2的方式计算可能因为left和right较大越界。