Loading... # 二分查找 待查找的序列是升序的,采用分治算法,时间复杂度为O(logN) ## 一个使用递归的版本 ```java public static int binarySearch1(int[] array, int toFind, int left, int right) { int mid = (right + left) / 2; // 基准情况 if (right - left == 1) { if (array[left] == toFind) return left; return -1; } if (array[mid] > toFind) { return binarySearch1(array, toFind, left, mid); } else if (array[mid] < toFind) { return binarySearch1(array, toFind, mid, right); } else { return mid; } } ``` ## 使用循环代替递归 ```java public static int binarySearch2(int[] array, int toFind) { int low = 0, high = array.length; while(low < high) { int mid = (low + high) / 2; if (array[mid] > toFind) { high = mid; } else if (array[mid] < toFind) { low = mid + 1; } else { return mid; } } return -1; } ``` 最后修改:2020 年 04 月 10 日 © 允许规范转载 赞 0 如果觉得我的文章对你有用,请随意赞赏