给定一个规模为n的按照数字从小到大排序的数组,快速查询x元素在数组中的位置
示例:
数组:[1,3,6,9,14,35,67] 查找的值:9输出:3 1、计算数据规模为n二分查找的时间复杂度循环次数 剩下的数据规模
第一次查找: T(1) = n/2
第二次查找: T(2) = n/2^2
第三次查找: T(3) = n/2^3
…
第M次查找: T(M) = n/2^M
数据规模大于等于1即 n/2^M >=1 ,说明不能再继续二分查找的操作,当数据规模达到最小值1时即n/2^M =1则是最坏的查找情况。
T(M) = n/2^M = 1 得到M=O(N)=log2n,二分查找的时间复杂度为以2为底数n为指数的对数。
2、算法如下 package com.example.algorithm;/** * 给定一个规模为n的按照数字从小到大排序的数组,快速查询x元素在数组中的位置 * <p> * 示例: * <p> * <p> * 数组:[1,3,6,9,14,35,67] * * <p> * <p> * 查找的值:9 * <p> * <p> * 输出:3 * * @author xukaijun5 * @since 2021/11/2 **/public class Day20211102 { public static int getIndex(int[] source, int target) { int left = 0; int right = source.length - 1; int mid; while (left <= right) { mid = (left + right) >> 1; if (source[mid] == target) { return mid; } else if (source[mid] > target) { right = mid - 1; } else { left = mid + 1; } } return -1; } public static void main(String[] args) { int[] source = new int[]{1, 3, 6, 9, 14, 35, 67}; System.out.println(getIndex(source, 9)); }}