查找---二分查找的三种实现和插值查找

小灰灰 2023-07-06 13:04 37阅读 0赞

#### 二分查找 ####

*  递归实现
 *  区间为左闭右闭
 *  区间为左闭右开

public class BinarySearchTest { 
        public static void main(String[] args) { 
            int[] arr = { 1,2,3,4,5};
            int index1 = binarySearch1(arr, 5);
            System.out.println(index1);
    
            int index2 = binarySearch2(arr, 5);
            System.out.println(index2);
    
            int index3 = binarySearchRecursion(arr, 5);
            System.out.println(index3);
        }
    
        //递归解法
        public static int binarySearchRecursion(int[] arr, int target) { 
            return binarySearch3(arr, 0, arr.length - 1, target);
        }
    
        public static int binarySearch3(int[] arr, int left, int right, int target) { 
            if(left > right) return -1;
    
            int mid = left + (right - left) / 2;
    
            if(arr[mid] > target) { 
                return binarySearch3(arr, left, mid - 1, target);
            }else if(arr[mid] < target) { 
                return binarySearch3(arr, mid + 1, right, target);
            }else { 
                return mid;
            }
        }
    
        //区间：左闭右闭
        public static int binarySearch1(int[] arr, int target) { 
            int left = 0;
            int right = arr.length - 1;
    
            while(left <= right) { 
                int mid = left + (right - left) / 2;
                if(arr[mid] == target) { 
                    return mid;
                } else if (arr[mid] < target) { 
                    left = mid + 1;
                }else{ 
                    right = mid - 1;
                }
            }
            return -1;
        }
    
        //区间：左闭右开
        public static int binarySearch2(int[] arr, int target) { 
            int left = 0;
            int right = arr.length;
    
            while(left < right) { 
                int mid = left + (right - left) / 2;
                if(target < arr[mid]) { 
                    right = mid;
                }else if(target > arr[mid]) { 
                    left = mid + 1;
                }else{ 
                    return mid;
                }
            }
    
            return -1;
        }
    }

#### 扩展题 ####

数组中有多个相同的目标值，把这些值的下标找出来，如\{1,2,2,3,4\} 目标值是2，则返回\{1,2\}

import java.util.ArrayList;
    import java.util.List;
    
    public class BinarySearchExtension { 
        public static void main(String[] args) { 
            int[] arr = { 1,2,2,3,4,4,4};
            List<Integer> result = binarySearchRecursion(arr, 3);
            System.out.println(result);
        }
        
        public static List binarySearchRecursion(int[] arr, int target) { 
            return binarySearch1(arr, 0, arr.length - 1, target);
        }
    
        public static List binarySearch1(int[] arr, int left, int right, int target) { 
            if(left > right) { 
                return new ArrayList<>();
            }
    
            int mid = left + (right - left) / 2;
            if(arr[mid] > target) { 
                return binarySearch1(arr, left, mid - 1, target);
            }else if(arr[mid] < target) { 
                return binarySearch1(arr, mid + 1, right, target);
            }else{ 
                int temp1 = mid - 1;
                int temp2 = mid + 1;
                int arrLen = arr.length;
                List<Integer> result = new ArrayList<>();
                //扫描mid左边的值
                while(temp1 >= 0 && arr[temp1] == target) { 
                    result.add(temp1);
                    temp1--;
                }
                result.add(mid);
                //扫描mid右边的值
                while(temp2 < arrLen && arr[temp2] == target) { 
                    result.add(temp2);
                    temp2++;
                }
                return result;
            }
        }
    }

#### 时间复杂度 ####

每次查找，元素个数减小一半，即n，n/2，n/4，…, n/2^ k，k就是循环的次数，取n/2^ k=1，即k=logn（以2为底），因此时间复杂度为O(logN)

#### 插值查找 ####

二分查找中取中间元素`mid= left + （right - left）/ 2`，设想这样一个例子：数据为1到1000，查找元素1，那么将会进行好几次循环才能找到1。于是有个改进的算法即插值算法：`mid=left + (right - left) * (target -arr[left]) / (arr[right] - arr[left])`，target是要找到目标值。  
对于数据量比较大，关键字分布比较均匀的查找来说，采用插值查找速度较快。关键字分布不均匀的情况下，该方法不一定比二分查找效率高。