数据结构与算法之二分查找法 复杂场景应用

对于一个不重复的有序数组，进行二分查找是最简单的，最容易些的，但是实际情况可能并不总是这么简单，而是多种复杂的情况。

情况一：查找目标数第一次出现的位置

之所以会有这样的情况，原因就在于要查找的有序数组中可能存在重复数据，所以通过二分查找到的数，可能是第一个数、最后一个数，或者是中间位置的数。

代码：

public static void main(String[] args) {
        int[] arrs = { 1,2,5,6,7,8,9,15,22,22,22,26,36};
        System.out.println("查找数的下标为:"+ search(arrs, 22));
    }

    public static int search(int[] arrs, int x) {
        int low = 0, high = arrs.length-1;
        while(low<=high) {
            //不使用(low+high)/2，是因为low+high有可能溢出
            int mid = low+((high-low)>>1);
            /*if(arrs[mid] == x) {
                return mid;
            }*/
            //这里的的low和high的复制如果直接复制mid，可能造成死循环，当查询的值不在数组中，就永远无法终止循环
            if(arrs[mid] > x) {
                high = mid-1;
            } else if(arrs[mid] < x) {
                low = mid+1;
            } else {
                //相等则判断前一个数是否还和x相等
                if(arrs[mid-1] == x) {
                    high = mid-1;
                } else {
                    return mid;
                }
            }
        }
        return -1;
    }

输出：

查找数的下标为:8

这里和之前的二分查找法代码的区别在于又多了一个else分支：

//相等则判断前一个数是否还和x相等
if(arrs[mid-1] == x) {
       high = mid-1;
} else {
       return mid;
}

这里的逻辑就是当发现相等的数，不马上返回，继续检查前一个数是否也相等，相等则继续循环查找。

情况二：查找目标数最后一次出现的位置

代码：

public static void main(String[] args) {
        int[] arrs = { 1,2,5,6,7,8,9,15,22,22,22,26,36};
        System.out.println("查找数的下标为:"+ search(arrs, 22));
    }

    public static int search(int[] arrs, int x) {
        int low = 0, high = arrs.length-1;
        while(low<=high) {
            //不使用(low+high)/2，是因为low+high有可能溢出
            int mid = low+((high-low)>>1);
            /*if(arrs[mid] == x) {
                return mid;
            }*/
            //这里的的low和high的复制如果直接复制mid，可能造成死循环，当查询的值不在数组中，就永远无法终止循环
            if(arrs[mid] > x) {
                high = mid-1;
            } else if(arrs[mid] < x) {
                low = mid+1;
            } else {
                //相等则判断前一个数是否还和x相等
                if(arrs[mid+1] == x) {
                    low = mid+1;
                } else {
                    return mid;
                }
            }
        }
        return -1;
    }

输出：

查找数的下标为:10

情况三：查找第一个大于等于目标数的位置

代码：

public static void main(String[] args) {
        int[] arrs = { 1,2,5,6,7,8,9,15,22,22,22,26,36};
        int x = 22;
        System.out.println(x+"查找数的下标为:"+ search(arrs, x));
        x=16;
        System.out.println(x+"查找数的下标为:"+ search(arrs, x));
    }

    public static int search(int[] arrs, int x) {
        int low = 0, high = arrs.length-1;
        while(low<=high) {
            //不使用(low+high)/2，是因为low+high有可能溢出
            int mid = low+((high-low)>>1);
            /*if(arrs[mid] == x) {
                return mid;
            }*/
            //这里的的low和high的复制如果直接复制mid，可能造成死循环，当查询的值不在数组中，就永远无法终止循环
            if(arrs[mid] >= x) {
                if(arrs[mid-1] >= x) {
                    high = mid-1;
                } else {
                    return mid;
                }
            } else {
                low = mid+1;
            }
        }
        return -1;
    }

输出：

22查找数的下标为:8
11查找数的下标为:7