查找：二分查找

思想

二分查找的思想很常见也很简单，使用分治思想从左边（中间元素大于目标元素）或者从右边（中间元素小于目标元素）查找元素。在一个顺序表中查找等于X的元素的index，从中间元素开始匹配，如果等于则直接返回，如果小于目标元素，则向左边区间查找，如果大于目标元素则向右边查找。

局限

首先，二分查找必须要使用数组，因为只有数组数据访问的时候时间复杂度是O(1)；
其次，二分查找依赖数组是有序的；
最后，数据量太大或者太小二分查找的性能优势不明显，数据量太小的时候，无法发挥O(logn)的性能优势，数据量太大的时候要大量的连续内存。

时间复杂度

每次缩小一半规模，时间复杂度为O(logn)

空间复杂度

没有额外的空间消耗，O(1)

实现

为了方便实现查找，定义接口如下

public interface LeeSearch {  
  
    <T extends Comparable<T>> int search(List<T> arr, T target);  
  
    <T extends Comparable<T>> int search(T[] arr, T target);  
  
}

实现如下：

package cn.lishiyuan.algorithm.search;  
  
  
import java.util.List;  
  
/**  
 * 二分查找  
 * <br>  
 * 从小于目标元素则向前查找，如果大于目标元素则向后查找，如何等于则直接返回。  
 *  
 */public class BinarySearch implements LeeSearch {  
  
    @Override  
    public <T extends Comparable<T>> int search(List<T> arr, T target) {  
        int size = arr.size();  
        int i = binarySearch(arr, target, 0, size - 1);  
        return i;  
    }  
  
    private <T extends Comparable<T>> int binarySearch(List<T> arr, T target, int low, int high){  
  
        if(low > high){  
            return -1;  
        }  
        // 取中  
        int mid = (low + high)/2;  
        if(arr.get(mid).compareTo(target) == 0){  
            return mid;  
        }  
        if(arr.get(mid).compareTo(target) < 0){  
            return binarySearch(arr, target, mid + 1,high);  
        }  
        return binarySearch(arr, target, low, mid - 1);  
    }  
  
    @Override  
    public <T extends Comparable<T>> int search(T[] arr, T target) {  
        int i = binarySearch(arr, target, 0, arr.length - 1);  
        return i;  
    }  
  
    private <T extends Comparable<T>> int binarySearch(T[] arr, T target, int low, int high){  
        // 取中  
        if(low > high){  
            return - 1;  
        }  
//        int mid = (low + high)/2;  
        // 防止int溢出的，(high - low) >> 1相当于给high和low的差值除以2  
        int mid = low + ((high - low) >> 1);  
        for(; low <= high; ){  
            if(arr[mid].compareTo(target) == 0){  
                return mid;  
            }  
            if(arr[mid].compareTo(target) < 0){  
                // 右边查找  
                low = mid + 1;  
            }else {  
                high = mid - 1;  
            }  
            mid = (low + high)/2;  
        }  
        return -1;  
    }  
}

变体

查找第一个等于X的元素的index

/**  
 * 给定一个元素，在有序集合中查找第一个等于给定元素的index  
 * <br>  
 * 思路是在等于之后不再终止而是继续向前查找，直到高位下标小于低位下标  
 * <br>  
 * 假设【1，3，4，5，5，5，6】中查找5，那么由于大于等于的时候区间会向前移动，小于的时候会向后移动。那么最终high=2，low=3时会结束查找  
 */  
public int first(List<T> list, T target){  
    int low = 0;  
    int high = list.size()-1;  
    // 开始查找  
    while(low <= high){  
        int mid = low + ((high - low) >> 1);  
        if(list.get(mid).compareTo(target) >= 0){  
            // 当前元素大于等于目标值，向前查找  
            high = mid - 1;  
        }else {  
            // 如果小于则向后查找  
            low = mid + 1;  
        }  
    }  
  
    // 如果没有越界且等于目标值，则返回。  
    if(low < list.size() && list.get(low).compareTo(target) == 0){  
        return low;  
    }  
  
    return -1;  
}

查找最后一个等于X的元素的index

/**  
 * 给定一个元素，在有序集合中查找最后一个等于给定元素的index  
 * <br>  
 * 思路是在等于之后不再终止而是继续向后查找，直到高位下标小于低位下标  
 * <br>  
 * 假设【1，3，4，5，5，5，6】中查找5，那么由于小于等于的时候区间会向后移动，大于的时候会向前移动。那么最终high=5，low=6时会结束查找  
 */  
public int last(List<T> list, T target){  
    int low = 0;  
    int high = list.size()-1;  
    // 开始查找  
    while(low <= high){  
        int mid = low + ((high - low) >> 1);  
        if(list.get(mid).compareTo(target) < 0){  
            // 如果小于等于则向后查找  
            low = mid + 1;  
        }else if(list.get(mid).compareTo(target) > 0) {  
            // 当前元素大于目标值，向前查找  
            high = mid - 1;  
        }else {  
            // 如果是最后一个元素 或者 后一个元素不等于则表示已经查找到最后一个等于当前元素的index  
            if(mid == (list.size() - 1) || list.get(mid+1).compareTo(target) != 0){  
                return mid;  
            }  
            // 否则继续向右查找  
            low = mid + 1;  
        }  
    }  
  
    return -1;  
}

查找最后一个小于等于X的元素的index

/**  
 * 给定一个元素，在有序集合中查找最后一个小于等于给定元素的index  
 * <br>  
 * 思路是在等于之后不再终止而是继续向后查找，直到高位下标小于低位下标  
 * <br>  
 * 假设【1，3，4，5，5，5，6】中查找5，那么由于小于等于的时候区间会向后移动，大于的时候会向前移动。那么最终high=5，low=6时会结束查找  
 */  
public int lastLte(List<T> list, T target){  
    int low = 0;  
    int high = list.size()-1;  
    // 开始查找  
    while(low <= high){  
        int mid = low + ((high - low) >> 1);  
        if(list.get(mid).compareTo(target) <= 0){  
            // 如果小于等于则向后查找  
            low = mid + 1;  
        }else {  
            // 当前元素大于目标值，向前查找  
            high = mid - 1;  
        }  
    }  
  
    // 如果没有越界且等于目标值，则返回。  
    if(high >= 0  && list.get(high).compareTo(target) >= 0){  
        return high;  
    }  
  
    return -1;  
}

查找第一个大于等于X的元素的index

/**  
 * 给定一个元素，在有序集合中查找第一个大于等于给定元素的index  
 * <br>  
 * 思路是在等于之后不再终止而是继续向前查找，直到高位下标小于低位下标  
 * <br>  
 * 假设【1，3，4，5，5，5，6】中查找第一个大于等于5的元素，那么由于大于等于的时候区间会向前移动，小于的时候会向后移动。那么最终high=2，low=3时会结束查找  
 *  
 */public int firstGte(List<T> list, T target){  
    int low = 0;  
    int high = list.size()-1;  
    // 开始查找  
    while(low <= high){  
        int mid = low + ((high - low) >> 1);  
        if(list.get(mid).compareTo(target) >= 0){  
            // 当前元素大于等于目标值，向前查找  
            high = mid - 1;  
        }else {  
            // 如果小于则向后查找  
            low = mid + 1;  
        }  
    }  
  
    // 如果没有越界且等于目标值，则返回。  
    if(low < list.size() && list.get(low).compareTo(target) >= 0){  
        return low;  
    }  
  
    return -1;  
}

总结

package cn.lishiyuan.leetcode;  
  
  
import java.util.List;  
  
  
/**  
 * 有序集合查找元素本质是在两个区间里面查找元素，一个合集总能分成小于(或等于)目标元素的部分和大于（或等于）目标元素的部分。  
 * <br>  
 * 查找元素的过程就是在左右两个部分中选择查找并逐渐缩小取钱的过程。  
 * @param <T>  
 */  
public class IndexOf<T extends  Comparable<T>> {  
    /**  
     * 给定一个元素，在有序集合中查找第一个等于给定元素的index  
     * <br>  
     * 思路是在等于之后不再终止而是继续向前查找，直到高位下标小于低位下标  
     * <br>  
     * 假设【1，3，4，5，5，5，6】中查找5，那么由于大于等于的时候区间会向前移动，小于的时候会向后移动。那么最终high=2，low=3时会结束查找  
     */  
    public int first(List<T> list, T target){  
        int low = 0;  
        int high = list.size()-1;  
        // 开始查找  
        while(low <= high){  
            int mid = low + ((high - low) >> 1);  
            if(list.get(mid).compareTo(target) >= 0){  
                // 当前元素大于等于目标值，向前查找  
                high = mid - 1;  
            }else {  
                // 如果小于则向后查找  
                low = mid + 1;  
            }  
        }  
  
        // 如果没有越界且等于目标值，则返回。  
        if(low < list.size() && list.get(low).compareTo(target) == 0){  
            return low;  
        }  
  
        return -1;  
    }  
  
  
    /**  
     * 给定一个元素，在有序集合中查找最后一个等于给定元素的index  
     * <br>  
     * 思路是在等于之后不再终止而是继续向后查找，直到高位下标小于低位下标  
     * <br>  
     * 假设【1，3，4，5，5，5，6】中查找5，那么由于小于等于的时候区间会向后移动，大于的时候会向前移动。那么最终high=5，low=6时会结束查找  
     */  
    public int last(List<T> list, T target){  
        int low = 0;  
        int high = list.size()-1;  
        // 开始查找  
        while(low <= high){  
            int mid = low + ((high - low) >> 1);  
            if(list.get(mid).compareTo(target) < 0){  
                // 如果小于等于则向后查找  
                low = mid + 1;  
            }else if(list.get(mid).compareTo(target) > 0) {  
                // 当前元素大于目标值，向前查找  
                high = mid - 1;  
            }else {  
                // 如果是最后一个元素 或者 后一个元素不等于则表示已经查找到最后一个等于当前元素的index  
                if(mid == (list.size() - 1) || list.get(mid+1).compareTo(target) != 0){  
                    return mid;  
                }  
                // 否则继续向右查找  
                low = mid + 1;  
            }  
        }  
  
        return -1;  
    }  
  
    /**  
     * 给定一个元素，在有序集合中查找第一个大于等于给定元素的index  
     * <br>  
     * 思路是在等于之后不再终止而是继续向前查找，直到高位下标小于低位下标  
     * <br>  
     * 假设【1，3，4，5，5，5，6】中查找第一个大于等于5的元素，那么由于大于等于的时候区间会向前移动，小于的时候会向后移动。那么最终high=2，low=3时会结束查找  
     *  
     */    public int firstGte(List<T> list, T target){  
        int low = 0;  
        int high = list.size()-1;  
        // 开始查找  
        while(low <= high){  
            int mid = low + ((high - low) >> 1);  
            if(list.get(mid).compareTo(target) >= 0){  
                // 当前元素大于等于目标值，向前查找  
                high = mid - 1;  
            }else {  
                // 如果小于则向后查找  
                low = mid + 1;  
            }  
        }  
  
        // 如果没有越界且等于目标值，则返回。  
        if(low < list.size() && list.get(low).compareTo(target) >= 0){  
            return low;  
        }  
  
        return -1;  
    }  
  
    /**  
     * 给定一个元素，在有序集合中查找最后一个小于等于给定元素的index  
     * <br>  
     * 思路是在等于之后不再终止而是继续向后查找，直到高位下标小于低位下标  
     * <br>  
     * 假设【1，3，4，5，5，5，6】中查找5，那么由于小于等于的时候区间会向后移动，大于的时候会向前移动。那么最终high=5，low=6时会结束查找  
     */  
    public int lastLte(List<T> list, T target){  
        int low = 0;  
        int high = list.size()-1;  
        // 开始查找  
        while(low <= high){  
            int mid = low + ((high - low) >> 1);  
            if(list.get(mid).compareTo(target) <= 0){  
                // 如果小于等于则向后查找  
                low = mid + 1;  
            }else {  
                // 当前元素大于目标值，向前查找  
                high = mid - 1;  
            }  
        }  
  
        // 如果没有越界且等于目标值，则返回。  
        if(high >= 0  && list.get(high).compareTo(target) >= 0){  
            return high;  
        }  
  
        return -1;  
    }  
  
}