常用算法

一，二分查找

public class HalfSearch {
    public static void main(String[] args) {
        HalfSearch hs = new HalfSearch();
        int a = hs.search(11);
        System.out.println(a);
    }
    
    // 二分查找
    public int search(int[] nums, int target) {
        if (nums == null || nums.length==0) {
            return -1;
        }
        
        int len = nums.length;
    
        int maxIndex = len-1;  // 一次二分后的最大索引
        int minIndex = 0; // 一次二分后的最小索引
    
        while (minIndex <= maxIndex) {
            // 计算中间索引，向下取整
            int midIndex = minIndex + (maxIndex - minIndex) / 2;

            if (nums[midIndex] == target) {
                return midIndex;
            }else if (nums[midIndex] < target){
                minIndex = midIndex+1;
            }else if (nums[midIndex] > target){
                maxIndex = midIndex -1;
            }
        }
        return -1;
    }
}

二，快排

public void quickSort(int [] arr,int low,int high) {
        if (low >= high) {
            return;//递归终止条件
        }
        int i = low;
        int j = high;//i,j分别定位在数组左边和数组右边
        int pivot = arr[low]; //pivot是基准元素的值，这里选择了arr[low]作为基准元素
        //接下来的过程就是比基准元素小的移到左边，大的移到右边
        while (i < j) {
            while (arr[j] >= pivot && i < j) {
                j--;
            }
            //指针j往左一直找，一直找到< pivot的元素停下
            while (arr[i] <= pivot && i < j) {
                i++;
            }
            //指针I往右一直找，一直找到>pivot的元素停下
            if (i < j) {
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
            //互换，这样小于pivot的元素到了相对靠左，大于pivot的元素到了相对靠右
        }
        //代码里加了多重判断i<j的限制。最终退出的时候可以推出I必然==j
        //把基准值arr[low]和此时的arr[i]交换位置，让基准值到达最终位置。可以看到，交换后arr[low]左侧元素均小于它，右侧元素均大于它
        //需要注意的是，while里的J循环必然在i循环之前，这是为了保证当i==j退出的时候对应的arr[i]元素小于arr[low]，而不是大于。
        arr[low] = arr[i];
        arr[i] = pivot;
        //此时pivot元素已经排好
        quickSort(arr,low,i - 1);
        quickSort(arr,i + 1,high);
        //递归快排子序列
    }