import java.util.ArrayList;
import java.util.List;

/**
 * @Author Gwl·Q
 * @ClassName SearchTest
 * @Date 2020/12/4 3:26 PM
 */
public class SearchTest {

    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < 10000; i++) {
            list.add(i);
        }
        Integer[] array = list.toArray(new Integer[list.size()]);
        boolean search = binarySearch(array, 44);
        System.out.println(search);
    }

    /**
     * 基本二分查找
     * @param array
     * @param target
     * @return:
     * @Date: 2020/12/4 3:17 PM
     */
    private static boolean binarySearch(Integer[] array, int target) {
        if (array == null || array.length == 0) {
            return false;
        }
        int low = 0, high = array.length - 1;
        while (low <= high) {
            // 避免相加数据过大
            int mid = low + (high - low) / 2;
            if (array[mid] == target) {
                return true;
            } else if (array[mid] > target) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return false;
    }

    /**
     * 查询第一个值等于指定值
     * @param array
     * @param target
     * @return:
     * @Date: 2020/12/4 3:17 PM
     */
    private static int binarySearchPlus1(Integer[] array, int target) {
        if (array == null || array.length == 0) {
            return -1;
        }
        int low = 0, high = array.length - 1;
        while (low <= high) {
            // 避免相加数据过大
            int mid = low + (high - low) / 2;
            if (array[mid] > target) {
                high = mid - 1;
            } else if (array[mid] < target) {
                low = mid + 1;
            } else {
                // 当前元素如果是第一个元素或者当前元素的前一个元素也等于目标元素，说明当前元素不是第一个值
                if (mid == 0 || array[mid - 1] != target) {
                    return mid;
                } else {
                    high = mid - 1;
                }
            }

        }
        return -1;
    }

    /**
     * 查询最后一个值等于指定值
     * @param array
     * @param target
     * @return:
     * @Date: 2020/12/4 3:17 PM
     */
    private static int binarySearchPlus2(Integer[] array, int target) {
        if (array == null || array.length == 0) {
            return -1;
        }
        int low = 0, high = array.length - 1;
        while (low <= high) {
            // 避免相加数据过大
            int mid = low + (high - low) / 2;
            if (array[mid] > target) {
                high = mid - 1;
            } else if (array[mid] < target) {
                low = mid + 1;
            } else {
                // 当前元素如果是最后一个元素或者当前元素的下一个元素也等于目标元素，
                // 说明当前元素不是最后一个值
                if (mid == array.length - 1 || array[mid + 1] != target) {
                    return mid;
                } else {
                    low = mid + 1;
                }
            }

        }
        return -1;
    }

    /**
     * 查找第一个大于等于给定值
     * @param array
     * @param target
     * @return:
     * @Date: 2020/12/4 3:36 PM
     */
    private static int binarySearchPlus3(Integer[] array, int target) {
        if (array == null || array.length == 0) {
            return -1;
        }
        int low = 0, high = array.length - 1;
        while (low <= high) {
            // 避免相加数据过大
            int mid = low + (high - low) / 2;
            if (array[mid] >= target) {
                // 判断mid可能是第一个元素或者mid前一个元素是小于给定值，
                // 则表示mid值是第一个大于等于给定值的元素
                if (mid == 0 || array[mid - 1] < target) {
                    return mid;
                } else {
                    high = mid - 1;
                }
            } else {
                low = mid + 1;
            }
        }
        return -1;
    }

    /**
     * 查找最后一个小于等于给定值
     * @param array
     * @param target
     * @return:
     * @Date: 2020/12/4 3:36 PM
     */
    private static int binarySearchPlus4(Integer[] array, int target) {
        if (array == null || array.length == 0) {
            return -1;
        }
        int low = 0, high = array.length - 1;
        while (low <= high) {
            // 避免相加数据过大
            int mid = low + (high - low) / 2;
            if (array[mid] > target) {
                high = mid - 1;
            } else {
                if (mid == array.length - 1 || array[mid + 1] > target) {
                    return mid;
                } else {
                    low = mid + 1;
                }
            }
        }
        return -1;
    }
}
