Java:[算法]二分查找 南京传媒学院-寇超杰
二分查找是一种算法，其输入是一个有序元素列表(必须有序)。查找成功返回其元素位置。
原理：
示例：[1,2,3,.......,98,99,100]
如果要查找一个1-100的数，假设从头开始查找，如果查找的数为99，那么需要99次才能成功。但如果从中间开始查找，从50开始，比较查找的数和50的大小，99大于50，这样就直接排除了一半的数字。再从51-100的中间数查找：75，99大于75，这样就又排除掉一半的数，以此类推，直到成功为止。这种算法查找1-100的任何数都可以在7次之内查找到，因为我们每次都排除掉一半的数字。这种算法叫做二分查找，时间复杂度为O(log2n);
而Java中有内置方法可以直接实现二分查找Arrays.binarySearch(object[ ], object key);
/*二分查找*/import java.util.Arrays;import java.util.Scanner;public class TwoPointLookup {public static void main(String[] args) {int[] arr = new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};/*int result = Arrays.binarySearch(arr, 8); //Java中自带的方法binarySearch就是二分查找System.out.println(result + 1); */ //.binarySearch(object[ ], object key);Scanner reader = new Scanner(System.in);int result = reader.nextInt();System.out.println(BinarySearch(arr, result));}/** @二分查找* @arr[] int数组* @result 需要查找的元素* @二分查找的数组必须是个有序数组* */private static int BinarySearch(int[] arr, int result) {int low = 0, high = arr.length - 1;while (low <= high) {int mid = (low + high) / 2;if (result > arr[mid]) {low = mid + 1;} else if (result < arr[mid]) {high = mid - 1;} else {return mid + 1;}}return 0;}}