算法-->折半查找（快排）

末蓝、 2022-06-12 12:22 206阅读 0赞

package 折半查找;
    
    import java.util.Scanner;
    
    public class ZheBan {
        static final int N = 15;
    
        static void quick(int[] arr, int left, int right) {
            int f, t;
            int rtemp, ltemp;
            ltemp = left;
            rtemp = right;
            f = arr[(rtemp + ltemp) / 2];// 确定分界值
            while (ltemp < rtemp) {
                while (arr[ltemp] < f) {
                    ++ltemp;
                }
                while (arr[rtemp] > f) {
                    --rtemp;
                }
                if (ltemp <= rtemp) {
                    t = arr[ltemp];
                    arr[ltemp] = arr[rtemp];
                    arr[rtemp] = t;
                    --rtemp;
                    ++ltemp;
                }
            }
            if (ltemp == rtemp) {
                ltemp++;
    
            }
            if (left < rtemp) {
                quick(arr, left, ltemp - 1);
            }
            if (ltemp < right) {
                quick(arr, rtemp + 1, right);
            }
        }
    
        static int search(int a[], int n, int x) {
            int low, mid, hight;
            low = 0;
            hight = n - 1;
            while (low <= hight) {
                mid = (low + hight) / 2;
                if (a[mid] == x) {
                    return mid;
                } else if (a[mid] > x) {
                    hight = mid - 1;
                } else {
                    low = mid + 1;
                }
            }
            return -1;
        }
    
        public static void main(String[] args) {
            ZheBan bb = new ZheBan();
            int[] shuzu = new int[N];
            int x, i, n;
            for (i = 0; i < N; i++) {
                shuzu[i] = (int) (100 + Math.random() * (100 + 1));
            }
            System.out.print("折半查找算法演示\n");
            System.out.print("排序前数据序列：\n");
            for (i = 0; i < N; i++) {
                System.out.print(" " + shuzu[i]);
            }
            System.out.print("\n\n");
            quick(shuzu, 0, N - 1);
            System.out.print("排序后的数据序列：\n");
            for (i = 0; i < N; i++) {
                System.out.print(" " + shuzu[i]);
            }
            System.out.print("\n\n");
            System.out.print("输入要查找的数：");
            Scanner sc = new Scanner(System.in);
            x = sc.nextInt();
            n = search(shuzu, N, x);
            if (n < 0) {
                System.out.println("没找到数据" + x);
            } else {
                System.out.println("数据" + x + "位于数组的第" + (n + 1) + " 个元素处");
            }
    
        }
    }

![这里写图片描述][SouthEast]

[SouthEast]: /images/20220612/5ce59fef7bec4f8590568512374114a0.png