Java8的Arrays.binarySearch()及其返回值分析

迈不过友情╰ 2022-01-23 09:21 231阅读 0赞

## 一、二分查找的返回值 ##

对有序数组应用二分查找是经典的查找算法，当查找的元素在数组中存在时，返回的是该元素在数组中的下标；如果查找的元素在数组中不存在时，此时的low下标其实是插入点（insertion point），即将查找元素插入该位置时，数组仍将保持有序，但有个问题，如果是返回0的话，被查找元素在数组到底有没有存在呢，针对这一问题Java8使用了一个小技巧，使得只要返回的下标值大于等于0就说明值在有序数组中存在。  
源码如下：

public static int binarySearch(int[] a, int fromIndex, int toIndex,
                                       int key) {
            rangeCheck(a.length, fromIndex, toIndex);
            return binarySearch0(a, fromIndex, toIndex, key);
        }
    
        // Like public version, but without range checks.
        private static int binarySearch0(int[] a, int fromIndex, int toIndex,
                                         int key) {
            int low = fromIndex;
            int high = toIndex - 1;
    
            while (low <= high) {
                int mid = (low + high) >>> 1;
                int midVal = a[mid];
    
                if (midVal < key)
                    low = mid + 1;
                else if (midVal > key)
                    high = mid - 1;
                else
                    return mid; // key found
            }
            return -(low + 1);  // key not found.
        }

**可以看到当key不存在时，返回的是-（insertion point + 1）**

## 二、变形应用 ##

上述代码中，low的位置是这样的：The insertion point is defined as the point at which the key would be inserted into the array: the index of the first element in the range **greater than** the key, or toIndex if all elements in the range are less than the specified key.  
因此，可以变形应用查找有序数组的元素插入位置，如剑指offer题目：`https://www.nowcoder.com/practice/70610bf967994b22bb1c26f9ae901fa2?tpId=13&tqId=11190&tPage=2&rp=2&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking`

import java.util.Arrays;
    
    public class Solution {
        
        public int binarySearch(int[] array, double key){
            int left = 0;
            int right = array.length - 1;
            int mid = left;
            while(left <= right){
                mid = (left + right) >>> 1;
                if(array[mid] == key) return mid;
                else if(array[mid] > key) right = mid -1;
                else left = mid + 1;
            }
            return left;
        }
        
        
        public int GetNumberOfK(int [] array , int k) {
            //要求要达到O(logn)的时间复杂度
            return binarySearch(array, k + 0.5) - binarySearch(array, k - 0.5);
        }
    }

## 三、基于源码返回值的应用 ##

基于上述分析，可以很轻易的在Arrays.binarySearch的基础上得到插入点的下标！

import java.util.Arrays;
    import java.util.Scanner;
    
    public class OneCounting {
        public static void main(String[] args) {
            int[] nums = {1, 2, 2, 4, 5, 6};
            Scanner in = new Scanner(System.in);
            while (in.hasNext()) {
                int x = in.nextInt();
                int idx = Arrays.binarySearch(nums, x);
                if (idx >= 0) {
                    System.out.println(x + "在数组中的下标是" + idx);
                } else {
                    int insertionPoint = -(idx + 1);
                    System.out.println(x + "不在数组中，插入点是" + insertionPoint);
                }
            }
    
        }
    }