二分法查找具有惊人的查找速度,尤其是对于海量数据的时候,作用更加明显,时间复杂度用大O表示法,即是(logn),这种(logn)时间复杂度是非常神奇的,比如 n 等于 2 的 32 次方,这个数很大了吧?大约是42亿,也就是说,如果我们在 42 亿个数据中用二分查找一个数据,最多需要比较 32 次。
但是,二分查找是有局限性的:
(1)二分查找依赖的是顺序表结构,简单点说就是数组。
解释:主要原因是二分查找算法需要按照下标随机访问元素。
(2)二分查找针对的是有序数据。
(3)数据量太小不适合二分查找。
(4)数据量太大也不适合二分查找。
解释:二分查找的底层需要依赖数组这种数据结构,而数组为了支持随机访问的特性,要求内存空间连续,对内存的空间要求比较苛刻。比如,我们有1GB的数据,那就需要1GB内存空间。
接下来是二分算法的代码了:
1 //二分法查找给定值 普通Java实现 2 public int bsearch(int[] a, int n, int value) { 3 int low = 0; 4 int high = n - 1; 5 6 while (low <= high) { 7 int mid = (low + high) / 2; 8 if (a[mid] == value) { 9 return mid; 10 } else if (a[mid] < value) { 11 low = mid + 1; 12 } else { 13 high = mid - 1; 14 } 15 } 16 17 return -1; 18 } 19 20 // 二分查找的递归实现 21 public int bsearch(int[] a, int n, int val) { 22 return bsearchInternally(a, 0, n - 1, val); 23 } 24 25 private int bsearchInternally(int[] a, int low, int high, int value) { 26 if (low > high) return -1; 27 28 int mid = low + ((high - low) >> 1); 29 if (a[mid] == value) { 30 return mid; 31 } else if (a[mid] < value) { 32 return bsearchInternally(a, mid+1, high, value); 33 } else { 34 return bsearchInternally(a, low, mid-1, value); 35 } 36 } 37 38 //查找第一个值等于给定值的元素 39 public int bsearch1(int[] a, int n, int value){ 40 int low = 0; 41 int high = n - 1; 42 43 while(low <= high){ 44 //这里用到的(右移)>>运算符 右移运算符简单理解就是 除以2的移动次幂 下面这个就是 等同于(high-low)/2^1 45 int mid = low + ((high-low) >> 1); 46 if(a[mid] > value){ 47 //说明value 在前半部分 把排好序的数组 从中间一切两半 48 high = mid - 1; 49 }else if(a[mid] < value){ 50 //说明value 在后半部分 51 low = mid + 1; 52 }else{ 53 //a[mid] == value 54 //但是我们要查找的是第一个 等于改定值的元素 还需要确认一下a[mid] 是不是第一个 55 if(mid == 0 || a[mid - 1] != value){ 56 //当mid == 0 的时候,说明这是第一个元素,肯定是我们要找的 57 //当a[mid] 前面的元素不等于 value的时候,说明a[mid]肯定就是第一个等于给定值的元素 58 //因为该数组是有序的,这里就是默认从小到大排序 59 return mid; 60 }else{ 61 high = mid - 1; 62 } 63 } 64 } 65 //这个 -1 代表的就是没有找到 66 return -1; 67 } 68 69 //查找最后一个值等于给定元素 70 public int bsearch2(int[] a, int n, int value){ 71 int low = 0; 72 int high = n - 1; 73 74 while(low <= high){ 75 int mid = low + ((low+high) >> 1); 76 if(a[mid] > value){ 77 high = mid - 1; 78 }else if(a[mid] < value){ 79 low = mid + 1; 80 }else{ 81 if(mid == n-1 || a[mid+1] != value){ 82 //同理 83 return mid; 84 }else{ 85 low = mid + 1; 86 } 87 } 88 } 89 return -1; 90 } 91 92 //查找第一个大于等于给定值的元素 93 public int bsearch3(int[] a, int n, int value){ 94 int low = 0; 95 int high = n - 1; 96 97 while(low <= high){ 98 int mid = low + ((low+high) >> 1); 99 if(a[mid] >= value){ 100 if(mid == 0 || a[mid-1] < value){ 101 //a[mid] 是第一个数,但是a[mid]大于等于value的数,所以肯定就是它了 102 //a[mid - 1] 是小于 value 的数,它的前一个数是小于value的,肯定也是它了 103 return mid; 104 }else{ 105 high = mid - 1; 106 } 107 }else{ 108 low = mid + 1; 109 } 110 } 111 return -1; 112 } 113 114 //查找最后一个小于等于给定值得元素 115 public int bsearch4(int[] a, int n, int value){ 116 int low = 0; 117 int high = n -1; 118 119 while(low <= high){ 120 int mid = low + ((low+high) >> 1); 121 if(a[mid] > value){ 122 high = mid - 1; 123 }else{ 124 if(mid == n-1 || a[mid+1] > value){ 125 //同理 126 return mid; 127 }else{ 128 low = mid + 1; 129 } 130 } 131 } 132 return -1; 133 }