查找算法

一、查找算法
1、顺序查找：最基本、最简单的查找方法
2、二分查找（折半查找）：

例:HDU2199

[java]
package D0705;

import java.util.Scanner;
import java.lang.Math;

public class HDU2199 {
//折半查找
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n;
        double y;
        double low, high, mid = 0;
        n = sc.nextInt();
        while (n-- > 0) {
            y = sc.nextDouble();
            low = 0;
            high = 100;
            if (y >= getResult(low) && y <= getResult(high)) {
                while (high - low >= 1e-6) {
                    mid = (low + high) / 2;
                    if (y == getResult(mid))
                        break;
                    else if (y < getResult(mid)) {
                        high = mid-1e-7;//不能写成high = mid-1e-6
                    } else {
                        low = mid+1e-7;//不能写成low = mid+1e-6
                    }
                }
                System.out.printf("%.4f", mid);
                System.out.println();
            } else {
                System.out.println("No solution!");
            }
        }

    }
    private static double getResult(double mid){
        double xr;
        xr = 8 * Math.pow(mid, 4) + 7 * Math.pow(mid, 3) + 2 * mid* mid + 3 * mid + 6;
        return xr;

    }

}

二分查找中还需要注意一个三分法：
例：HDU2899

[java]
package D0705;

import java.util.Scanner;

public class HDU2899 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t;
        double y, high, low, mid, mid2;
        t = sc.nextInt();
        while (t-- > 0) {
            y = sc.nextDouble();
            high = 100;
            low = mid = mid2 = 0;
            double min = 0;// 最终的最小结果
            while (high - low >= 1e-6) {
                mid = (low + high) / 2;// 二分查找
                mid2 = (mid + low) / 2;// 二分查找中的二分查找（三分法）
                min = getFx(mid, y);
                double min2 = getFx(mid2, y);
                if (min2 > min) {// 如果min2>min则最小值必定落在mid2到high之间，
                    low = mid2;
                } else
                    // 否则，最小值必定落在low到mid之间
                    high = mid;
            }
            System.out.printf("%.4f", min);
            System.out.println();
        }

    }

    private static double getFx(double x, double y) {
        double fx = 6 * Math.pow(x, 7) + 8 * Math.pow(x, 6) + 7
                * Math.pow(x, 3) + 5 * Math.pow(x, 2) - y * x;
        return fx;
    }
}

当然还有很多别的查找方法：由于lz水

作者：lhfight

补充：软件开发 , Java ,