二分查找Java版本

二分查找

* 二分查找
* 特点，数组有序（升序）

基础版

public static int binarySearchBasic(int[] a, int target) {
    //定义边界
    int left = 0, right = a.length;

    //判断边界是否有值
    while (left < right) {
        int mid = (left+right) >>> 1;
        if (a[mid] > target) right = mid; //目标在左边
        else if (a[mid] < target) left = mid + 1; //目标在右边
        else return mid;
    }

    return -1;
}

平衡板

* 平衡二分查找
* 特点：左边和右边的执行次数一样
* 优点：减少循环内的平均次数

public static int binarySearchBasic2(int[] a, int target) {
    int left = 0,right = a.length;
    while (1<right-left){
        int mid = (right+left)>>>1;
        if (target <a[mid]){
            right = mid ;
        }else {
            left = mid;
        }
    }
    if (a[left]== target){
        return left;
    }else {
        return -1;
    }
}

LeftMost

/*
* 找到重复元素最左侧元素下标
* 找不到返回 -1
* */

public static int LeftMostBinarySearchBasic(int[] a, int target) {
    //定义边界
    int left = 0, right = a.length-1;
    //目标下标
    int index = -1;
    //判断边界是否有值
    while (left <= right) {
        int mid = (left+right) >>> 1;
        if (a[mid] > target) right = mid-1; //目标在左边
        else if (a[mid] < target) left = mid + 1; //目标在右边
        else { index = mid; //记录下标
               right = mid - 1; //左移下标，查找最左边的值
        }
    }
    return index;
}

/**
 *
 * @param a  待查找的升序数组
 * @param target  待查找的目标值
 * @return  返回>=target 最靠左的索引位置
 */

public static int LeftMostBinarySearchBasic2(int[] a, int target) {
    //定义边界
    int left = 0, right = a.length;
    //判断边界是否有值
    while (left < right) {
        int mid = (left+right) >>> 1;
        if (a[mid] >= target) right = mid -1; //目标在左边
        else if (a[mid] < target) left = mid + 1; //目标在右边
    }
    return left;
}

RightMost

/*
 * 找到重复元素最右侧元素下标
 * 找不到返回 -1
 * */

public static int RightMostBinarySearchBasic(int[] a, int target) {
    //定义边界
    int left = 0, right = a.length-1;
    //目标下标
    int index = -1;
    //判断边界是否有值
    while (left <= right) {
        int mid = (left+right) >>> 1;
        if (a[mid] > target) right = mid-1; //目标在左边
        else if (a[mid] < target) left = mid + 1; //目标在右边
        else {
            index = mid; //记录下标
            left = mid + 1; //右移下标，查找最右边的值
        }
    }
    return index;
}

/**
 * @param a      待查找的升序数组
 * @param target 待查找的目标值
 * @return 返回< =target 最靠右的索引位置
 */

public static int RightMostBinarySearchBasic2(int[] a, int target) {
    //定义边界
    int left = 0, right = a.length;
    //判断边界是否有值
    while (left < right) {
        int mid = (left + right) >>> 1;
        if (a[mid] > target) right = mid - 1; //目标在左边
        else left = mid + 1; //目标在右边
    }
    return right;
}

LeftRightMost应用

名词解释

• 前任：比目标值小的，更靠右的
• 后任：比目标值大的，更靠左的
• 最近邻居：前后任相比，更小的

leftmost — 求排名

求目标数排名

求排名: leftmost(4) = 2 +1
leftmost(5) = 5 +1

即 leftmost(*) + 1

leftmost — 求前任

求前任：leftmost(4) -1

​ leftmost(5) -1

rightmost — 后前任

求前任：rightmost(4）+1

​ rightmost(5) +1