import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Random;

/**
 * @Author Gwl·Q
 * @ClassName test
 * @Date 2020/11/20 10:54 AM
 */
public class Test {

    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();
        Random random = new Random();
        for (int i = 0; i < 100000; i++) {
            list.add(i);
        }
        /*Integer[] sort = mergeSort(list.toArray(new Integer[list.size()]));
        Integer[] sort1 = quickSort(list.toArray(new Integer[list.size()]), 0,list.size() - 1);
        System.out.println(Arrays.toString(sort1));*/
        int find = 0;
        int count = 0;
        Integer[] array = list.toArray(new Integer[list.size()]);
        int low = 0, high = array.length - 1;
        while (low <= high) {
            int mid = (low + high ) / 2;
            count++;
            if (array[mid] == find) {
                System.out.println("count:" + count);
                break;
            } else if (array[mid] < find) {
                low = mid + 1;

            } else {
                high = mid - 1;
            }
        }
    }

    public static Integer[] shellSort(Integer[] array) {
        if (array == null || array.length == 0) {
            return new Integer[0];
        }
        int gap = array.length / 2;
        while (gap > 0){
            for(int i = gap;i< array.length;i++){
                int temp = array[i];
                int preIndex = i - gap;
                while (preIndex >=0 && temp < array[preIndex]){
                    array[gap + preIndex] = array[preIndex];
                    preIndex -= gap;
                }
                array[gap + preIndex] = temp;
            }
            gap /= 2;
        }
        return array;
    }

    public static Integer[] mergeSort(Integer[] array) {
        if(array.length < 2){
            return array;
        }
        int mid = array.length / 2;
        Integer[] left = Arrays.copyOfRange(array,0, mid);
        Integer[] right = Arrays.copyOfRange(array, mid, array.length);
        return merge(mergeSort(left),mergeSort(right));
    }

    private static Integer[] merge(Integer[] left, Integer[] right) {
        Integer[] merge = new Integer[left.length + right.length];
        for (int index = 0, i = 0, j = 0; index < merge.length; index++) {
            if (i >= left.length) {
                merge[index] = right[j++];
            } else if (j >= right.length) {
                merge[index] = left[i++];
            } else if (left[i] > right[j]) {
                merge[index] = right[j++];
            } else {
                merge[index] = left[i++];
            }
        }
        return merge;
    }

    public static Integer[] quickSort(Integer[] array, int start, int end) {
        if (array == null || array.length == 0 || start < 0 || end >= array.length || start > end) {
            return null;
        }
        int swapIndex = partition(array, start, end);
        if (swapIndex > start) {
            quickSort(array, start, swapIndex - 1);
        }
        if (swapIndex < end) {
            quickSort(array, swapIndex + 1, end);
        }
        return array;
    }

    private static int partition(Integer[] array, int start, int end) {
        int pivot = (int) (start + Math.random() * (end - start + 1));
        int swapIndex = start - 1;
        swap(array, pivot, end);
        for (int i = start; i < array.length; i++) {
            if (array[i] <= array[end]) {
                swapIndex++;
                if (i > swapIndex) {
                    swap(array, swapIndex, i);
                }
            }
        }
        return swapIndex;
    }

    private static Integer[] swap(Integer[] array, int swap1, int swap2) {
        int temp = array[swap1];
        array[swap1] = array[swap2];
        array[swap2] = temp;
        return array;
    }


}
