基础算法（三）---二叉树搜索（Java）

二分查找算法是一种在有序数组中查找某一特定元素的搜索算法。

算法步骤：

搜素过程从数组的中间元素开始： 如果中间元素正好是要查找的元素，则搜素过程结束； 如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。 如果在某一步骤数组为空，则代表找不到。

这种搜索算法每一次比较都使搜索范围缩小一半。折半搜索每次把搜索区域减少一半，时间复杂度为Ο(logn) 。

public class BinarySearch { public static <T extends Comparable<? super T>> int binarysearch(T[] a, T x) { final int NOT_FOUND = -1; int low = 0; int high = a.length - 1; while (low <= high) { int mid = (low + high) / 2; if (a[mid].compareTo(x) < 0) { low = mid + 1; } else if (a[mid].compareTo(x) > 0) { high = mid - 1; } else { return mid; } } return NOT_FOUND; } }