不一样的二分查找

心已赠人 2023-02-09 13:17 21阅读 0赞

## 不一样的二分查找 ##

> 大家肯定一定非常熟悉二分查找法，如果面试官让你写个二分查找法，估计你会在被子里偷笑，但是如果让人查找目标值的最小索引，即如果有多个相同值，直接返回最小的索引。可以直接查出来任意一个目标值，然后向左遍历，但是还有一种优雅的方式，只要改动一两行代码

### 普通二分查找法 ###

//最普通的二分查找法
    public static boolean binarySearch(int start, int end, int[]arr, int target) { 
        if(start > end) return false;
    
        int middle = (start + end) / 2;
    
        if(arr[middle] == target) return true;
        if(arr[middle] > target) return binarySearch(start, middle-1, arr, target);
        if(arr[middle] < target) return binarySearch(middle+1, end, arr, target);
    
        return false;
    }

### 查找左边界的值 ###

//找左侧边界
    //arr =[2, 3, 4, 4, 5, 6] target = 4, 则左侧边界为2
    public static int binarySearchLeft(int start, int end, int[]arr, int target) { 
        if(start == end) { 
            if(arr[start] != target) return -1;
            else return start;
        }
    
        int middle = (start + end) / 2;
    
        if(arr[middle] == target) return binarySearchLeft(start, middle, arr, target);
        if(arr[middle] > target) return binarySearchLeft(start, middle-1, arr, target);
        if(arr[middle] < target) return binarySearchLeft(middle+1, end, arr, target);
    
        return -1;
    }

### 查找右边界的值 ###

//找右侧边界
    //arr =[2, 3, 4, 4, 5, 6] target = 4, 则右侧边界为3
    public static int binarySearchRight(int start, int end, int[]arr, int target) { 
        if(start == end) { 
            if(arr[start] != target) return -1;
            else return start;
        }
    
        int middle = (start + end) / 2;
    
        if(arr[middle] == target) return binarySearchRight(middle, end, arr, target);
        if(arr[middle] > target) return binarySearchRight(start, middle-1, arr, target);
        if(arr[middle] < target) return binarySearchRight(middle+1, end, arr, target);
    
        return -1;
    }