java实现二分法查找

时间:2022-10-27 16:36:53

一 前提

使用二分法查找的前提是:有序的数组,没有重复的数据元素。
如果没有排序过的,需先排序。

二分法查找时使用场景为:数据量较大时

二 代码

 1 package com.xiao.day01;
 2 
 3 public class DichotomySearch {
 4 
 5     public static void main(String[] args) {
 6            int[] arr = new int[] { 12, 23, 34, 45, 53, 67, 77, 89, 90 };
 7            System.out.println(search(arr, 34));
 8            /*System.out.println(search(arr, 45));
 9            System.out.println(search(arr, 67));
10            System.out.println(search(arr, 89));
11            System.out.println(search(arr, 99));*/
12        }
13 
14         /**
15          * 
16          * @param arr
17          * @param key
18          * @return middle 为数组下标值(0,1,2...)
19          */
20        public static int search(int[] arr, int key) {
21            int start = 0;
22            int end = arr.length - 1;
23            while (start <= end) {
24                int middle = (start + end) / 2;
25                if (key < arr[middle]) {
26                    end = middle - 1;
27                } else if (key > arr[middle]) {
28                    start = middle + 1;
29                } else {
30                    return middle;
31                }
32            }
33            return -1;
34        }
35 }

参考网址