JAVA实现折半查找算法

package demo;

import java.util.Scanner;

public class wdnmd2 {
    public static void main(String[] args) {
        int[] arr = {10, 20, 30, 40, 50, 60};
        Scanner sc = new Scanner(System.in);
        System.out.println("请输入一个数");
        int n = sc.nextInt();
        int s = select(arr, n);
        if (s > 0) {
            System.out.println("找到了" + n);
        } else System.out.println("没找到" + n);
    }

    public static int select(int[] arr, int n) {
        int minindex = 0;
        int maxindex = arr.length - 1;
        int midindex;
        while (minindex <= maxindex) {
            midindex = (minindex + maxindex) / 2;
            if (n > arr[midindex]) {
                minindex = midindex + 1;
            } else if (n < arr[midindex]) {
                maxindex = midindex - 1;
            } else if (n == arr[midindex]) {
                return arr[midindex];
            }
        }
        return -1;
    }

}

运算结果：

解析：折半查找算法的前提是排序后的数组，每次拿查找元素和中间元素去比较，然后改变索引**

第一种情况：查找元素==中间索引所对应的元素，则查找成功

第二种情况：查找元素<中间索引所对应的元素，则要改变最大索引，maxindex=midindex-1；

第三种情况：查找元素>中间索引所对应的元素，则要改变最小索引，minindex=midindex+1；

     折半查找

1. 首先用要查找的关键字值(key)与中间位置结点的关键字值(arr[mid])相比较；
2. 若比较结果相等，则查找完成；若不相等，再根据要查找的关键字值(key)与该中结点关键值(mid)的大小来确定下一步在那个子表中进行；
3. 若待查关键值大于中间结点的关键字值(key > arr[mid])),则应查找中间结点以后的字表，否则（key < arr[mid])），查找中间结点以前的字表；
4. 重复步骤1~3，直到找到满足条件的结点，或者明确表中没有这样的结点。

5. 图解：

    //折半查找
    public static void main(String[] args) {
        int[] arr = {2,6,3,1,8,9,10};
        int index = binarySearch(arr,8);
        System.out.print(index);//输出 4

    }
    /**
     * 
     * @param arr 要进行查找的数组，要求数组必须是有序的
     * @param key 要查找的元素
     * @return 返回要查找的元素在数组的索引位置， 返回-1表示没找到
     */
    public static int binarySearch(int[] arr,int key){
        int low = 0;
        int high = arr.length - 1;
        int mid;
        while (low <= high) {
            mid = (low + high) / 2;
            if (key < arr[mid]) {
                high = mid - 1;
            }
            if (key > arr[mid]) {
                low = mid + 1;
            }
            if (arr[mid] == key) {
                return mid;
            }
        }
        return -1;
    }