二分查找的实现方式

二分查找（Binary Search）是一种常见的算法，在查找有序数组（或集合）中的某个元素时，可以通过二分查找快速找到该元素，时间复杂度为O(log n)。本文将从多个角度分析二分查找的实现方式。

一、基本思想

二分查找的基本思想是将查找区间一分为二，每次比较中间位置的值与目标值的大小，对于小于目标值的部分舍弃，对于大于目标值的部分舍弃，缩小查找区间，直到找到目标值或者区间为空。

示例代码如下：

```java

public int binarySearch(int[] nums, int target) {

int left = 0;

int right = nums.length - 1;

while (left <= right) {

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

if (nums[mid] == target) {

return mid;

} else if (nums[mid] < target) {

left = mid + 1;

} else {

right = mid - 1;

}

}

return -1;

}

```

二、实现方式

1. 迭代实现

上述示例代码为迭代实现方式，利用循环进行区间缩小和比较操作，直到找到目标元素或区间为空。

2. 递归实现

二分查找也可以使用递归方式实现。递归实现时，需要判断递归终止的条件，否则可能会进入死循环。

示例代码如下：

```java

public int binarySearch(int[] nums, int target, int left, int right) {

if (left > right) {

return -1;

}

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

if (nums[mid] == target) {

return mid;

} else if (nums[mid] < target) {

return binarySearch(nums, target, mid + 1, right);

} else {

return binarySearch(nums, target, left, mid - 1);

}

}

```

三、优化方式

1. 位运算替代除法运算

在计算中间位置时，可以使用位运算替代除法运算，提高运算效率。如下所示：

```java

int mid = (left + right) >>> 1;

```

2. 双指针优化

在二分查找时，可以使用两个指针来缩小查找区间，提高查找效率。如下所示：

```java

public int binarySearch(int[] nums, int target) {

int left = 0;

int right = nums.length - 1;

while (left < right) {

int mid = (left + right) >>> 1;

if (nums[mid] == target) {

return mid;

} else if (nums[mid] < target) {

left = mid + 1;

} else {

right = mid - 1;

}

}

return nums[left] == target ? left : -1;

}

```

四、注意点

1. 数组越界

需要注意数组越界的情况，在计算中间位置时要确保left和right的范围。

2. 死循环

递归实现时，需要确保递归终止条件正确，否则可能会陷入死循环。