java - 二分查找

一、什么是二分查找

二、代码实现  

非递归：

 public static int binarySearch(int[] array,int target){
        int i = 0;
        int j = array.length-1;
        while(i <= j){
            int mid = (i+j) / 2;
            if(target > array[mid]){
                i = mid + 1;
            }else if(target < array[mid]){
                j = mid - 1;
            }else{
                return mid;
            }
        }
        return -1;
    }

递归：

   public static int binarySearch(int[] array,int left,int right,int target){
        if(left > right){
            return  -1;
        }
        int mid = (left+right)/2;
        if(target > array[mid]){
            left = mid + 1;
        }else if(target < array[mid]){
            right = mid-1;
        }else{
            return mid;
        }
      return binarySearch(array,left,right,target);
    }

三、算符特性

时间复杂度：O(log n)，在二分循环中，区间每轮缩小一半，循环次数为 log n 。 

空间复杂度：O(1)，指针 i 和 j 使用常数大小空间。

四、优点与局限性

 二分查找在时间和空间方面都有较好的性能。

• 二分查找的时间效率高。在大数据量下，对数阶的时间复杂度具有显著优势。例如，当数据大小 n=2^20 时，线性查找需要 2^20=1048576 轮循环，而二分查找仅需 log(2)2^20=20 轮循环。
• 二分查找无须额外空间。相较于需要借助额外空间的搜索算法（例如哈希查找），二分查找更加节省空间。

然而，二分查找并非适用于所有情况，主要有以下原因。

• 二分查找仅适用于有序数据。若输入数据无序，为了使用二分查找而专门进行排序，得不偿失。因为排序算法的时间复杂度通常为 O(n ^ log⁡ n) ，比线性查找和二分查找都更高。对于频繁插入元素的场景，为保持数组有序性，需要将元素插入到特定位置，时间复杂度为 O(n) ，也是非常昂贵的。
• 二分查找仅适用于数组。二分查找需要跳跃式（非连续地）访问元素，而在链表中执行跳跃式访问的效率较低，因此不适合应用在链表或基于链表实现的数据结构。
• 小数据量下，线性查找性能更佳。在线性查找中，每轮只需要 1 次判断操作；而在二分查找中，需要 1 次加法、1 次除法、1 ~ 3 次判断操作、1 次加法（减法），共 4 ~ 6 个单元操作；因此，当数据量 n 较小时，线性查找反而比二分查找更快。

 参考：