# article: true title: 算法: Binary Search icon: fa6-solid:repeat

• binary search，也称作二分法（half-interval search），每次划分一半进行下一步搜索，所以时间复杂度无非就是while循环的次数！
• 
  • maximum comparisons are dependent on the height of a tree logn，极端情况下我们需要查找所有n个elements得到target.
    • 第一次折半查找的为区间n，比较次数 c=1（中间值可能的个数为：2^c - 1 = 1， index: [8]）
    • 第二次折半查找的为区间n/2，比较次数 c=2（中间值可能的个数为：2^c - 1 = 3，index: [8, 4, 12]）
      • if target <= mid point: (left point, mid point-1) 即( 1, 7)
      • or target >= mid point: (mid point+1, right point) 即( 9, 15)
      • 一共可能的区间个数为2 ， 即( 1, 7) or (9, 15)
    • 第三次次折半查找的为区间n/4，比较次数 c=3（中间值可能的个数为：2^c - 1 = 7，index: [8, 4, 12, 2, 6, 10, 14]）
      • if target <= mid point: (left point, mid point-1)
      • or target >= mid point: (mid point+1, right point)
      • 一共可能的区间个数为4 ， 即( 1, 3) or (5, 7) or ( 9, 11) or (13, 15)
    • 第四次次折半查找的为区间n/8，比较次数 c=4（中间值可能的个数为：2^c - 1 = 15，index: [8, 4, 12, 2, 6, 10, 14, 1, 3, 5, 7, 9, 11, 13, 15]）
      • if target <= mid point: (left point, mid point-1)
      • or target >= mid point: (mid point+1, right point)
      • 一共可能的区间个数为8 ， 即 (1,1) or (3,3) or (5,5) or (7,7) or (9,9) or (11,11) or (13,13) or (15,15)
      • 数组只余一个元素无法再分，计算结束。
      • 此时中间值可能的个数=元素总个数len(nums), 算法经历了所有可能值
  • 总共有n个元素，每次查找的区间大小为n，n/2，n/4，…，n/2^c 且2^c_max - 1 = len(nums) 可得 c=log2(n+1), n+1为常数所以可以把它看作c=log2(n),（ c为比较的次数or循环的次数or二分树的高度），log2(n)中2可以省略所以时间复杂度为 O(logn)
    • minimum time of binary search: 1次比较得到target, O(1)
    • maximum time of binary search: log(n)次比较得到target, O(logn)