4.20Java二分法查找

什么是二分法查找

二分法检索(binary search)称折半检索

二分法查找的基本思想

前提：

• 数组中的元素从小到大有序的存放在数组(array)中

步骤：

• 将给定值key与数组中间位置元素的关键码(key)比较

• 如果相等，检索成功

• key小，在数组前半段继续二分查找

• key大，在数组后半段进行二分查找，直到索引成功

对于有序数组而言，二分查找的效率是比较高的

实例：

package com.array;
?
import java.util.Arrays;
?
/**
 * 测试二分法查找，折半检索,通过值找索引
 * @author Lucifer
 */
public class TestBinarySearch {
    public static void main(String[] args) {
?
        /*测试源数组*/
        int[] arr = {30,20,50,10,80,9,7,12,100,40,8};
?
        /*
        1.排序---不用冒泡排序，用工具类方法
        2.定义检索的范围---定义两个变量，起始位置、结束位置
         */
        Arrays.sort(arr);
?
        //要查找的值
//        int value = 10;
?
        System.out.println(Arrays.toString(arr));
        System.out.println();
?
        /*封装返回值*/
        /*
        传进来的值进行查找
        在arr数组中查找
        这样就定义了形参
         */
        public static int myBinarySearch(int[] arr, int value){
?
            /*测试二分查找*/
?
            //起始位置
            int low = 0;
?
            //结束位置
            int high = arr.length - 1; //最大索引值
?
            //循环条件
            while (low <= high){
?
                //定义中间索引值
                int mid = (low + high)/2;
?
                //相等说明找到了，直接返回值
                if (value == arr[mid]){
                    return mid;
                }
?
                //如果值比中间索引值要大，说明要从中间索引向后找，所以起始位置索引要变成中间索引值+1
                if (value > arr[mid]){
                    low = mid + 1;
                }
?
                //如果值比中间索引值小，说明要从中间索引向前找，所以起始位置索引要变成中间索引值-1
                if (value < arr[mid]){
                    low = mid - 1;
                }
?
            }
            //没有找到返回-1
            return -1;
        }
    }
}

4.20Java二分法查找

原文：https://www.cnblogs.com/JunkingBoy/p/14682614.html