【剑指Offer】查找算法——二分查找
一、算法简介
二分查找又叫折半查找，需求待查找的序列有序。每次取中间位置的值与待查关键字比较，如果中间位置的值比待查关键字大，则在前半部分循环这个查找的过程，如果中间位置的值比待查关键字小，则在后半部分循环这个查找过程。直到查找到了为止，否则序列中没有待查的关键字。
二、时间复杂度
由于二分查找每次查询都是从数组中间切开查询，所以每次查询，剩余的查询数为上一次的一半，从下表可以清晰的看出查询次数与剩余元素数量对应关系
表-查询次数及剩余数
第几次查询 剩余待查询元素数量
1 |
N/2 |
2 |
N/(2^2) |
3 |
N/(2^3) |
4 |
… |
5 |
N/(2^K) |
从上表可以看出N/(2^K)肯定是大于等于1，也就是N/(2^K)>=1，我们计算时间复杂度是按照最坏的情况进行计算，也就是是查到剩余最后一个数才查到我们想要的数据，也就是
N/(2^K)=1
=>N=2^K
=>K=log2N
所以二分查找的时间复杂度为O(log2N)
三、代码实现
package cn.dzp.flyroc.search;import java.util.Scanner;public class BinarySearchDemo {public static void main(String[] args) {int[] arr = {2, 3, 6, 8, 11, 65, 32, 97, 100};Scanner scanner = new Scanner(System.in);binarySearch(arr, scanner.nextInt());}//二分查找public static void binarySearch(int[] arr, int key) {int low = 0;int high = arr.length;for (int i = 0; i < high;){ //先遍历这个数组，判断这个元素是否存在if (arr[i] != key){if (i == high-1){ //当遍历到数组最后一个索引时System.out.println("不存在这个元素");return;}i++;}else { //这个元素在数组中存在int mid; //定义中间值while (low <= high){mid = (low+high)>>1; //求中间值if (arr[mid] == key){System.out.println(key+"元素对应的索引是："+mid);return;}else if (arr[mid] < key){ //中间值小low = mid +1;}else { //中间值大high = mid -1;}}}}}}
【剑指Offer】算法系列，本人会持续写出代码实现过程，敬请期待，请持续关注大数据健身侠：