一 前提
使用二分法查找的前提是:有序的数组,没有重复的数据元素。
如果没有排序过的,需先排序。
二分法查找时使用场景为:数据量较大时
二 代码
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 }