# （簡單）704. 二分查找
題目鏈接
代碼隨想錄 - 二分查找思路
二分查找，思路很簡單，但是在while循環(huán)left和right的比較是寫<=還是<，還有right=mid還是right=mid-1容易混淆
需要想清楚對區(qū)間的定義，是[left,right]，還是[left,right)
（版本一，左閉右閉版本）
class Solution {
public int search(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
int mid;
while (left <= right) {
mid = left + ((right-left)/2);//防止溢出
if (nums[mid] == target) {
return mid;
}
if (target > nums[mid]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
}
（版本二，左閉右開）
class Solution {
public int search(int[] nums, int target) {
//避免當(dāng)target小于nums[0] 或者大于 nums[nums.length-1]時(shí) 多次循環(huán)
if (target < nums[0] || target > nums[nums.length - 1]) {
return -1;
}
int left = 0;
int right = nums.length;
int mid;
while (left < right) {
mid = left + ((right - left) >> 1);
if (nums[mid] == target) {
return mid;
}
if (target > nums[mid]) {
left = mid + 1;
} else {
right = mid;
}
}
return -1;
}
}
（簡單）35. 搜索插入位置
題目鏈接
class Solution {
public int searchInsert(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
int mid;
while (left <= right) {
mid = left + ((right - left) >> 1);
if (nums[mid] == target) {
return mid;
}
if (target > nums[mid]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return left;//right+1
}
}
（*中等）34. 在排序數(shù)組中查找元素的第一個(gè)和最后一個(gè)位置
題目鏈接
我的思路：按照傳統(tǒng)二分查找的方式，找到等于target的數(shù)組的下標(biāo)，然后向兩邊擴(kuò)展，如果沒找到直接返回[-1,-1]
class Solution {
public int[] searchRange(int[] nums, int target) {
//如果數(shù)組長度是0，則不用判斷
if (nums == null || nums.length == 0) {
return new int[]{-1, -1};
}
//如果target的值小于第一個(gè)元素或者大于最后一個(gè)元素，也不用判斷
if ((target < nums[0]) || (target > nums[nums.length - 1])) {
return new int[]{-1, -1};
}
int res = search(nums, target);
if (res == -1) {
return new int[]{-1, -1};
}
int left = res;
int right = res;
while ((left >= 0) && (nums[left] == nums[res])) {
left--;
}
while ((right < nums.length) && (nums[right] == nums[res])) {
right++;
}
return new int[]{left + 1, right - 1};
}
public int search(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
int mid;
while (left <= right) {
mid = left + ((right - left) >> 1);
if (target == nums[mid]) {
return mid;
}
if (target > nums[mid]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
}
看了官方的解題思路，是找出數(shù)組中【第一個(gè)等于target的位置（leftIdx）】和【第一個(gè)大于target的位置減一（rightIdx）】
二分查找中
- 尋找leftIdx即為在數(shù)組中尋找第一個(gè)大于等于 target的下標(biāo)
- 尋找rightIdx即為在數(shù)組中尋找第一個(gè)大于 target的下標(biāo)，然后減一
二者的判斷條件不同，為了代碼的復(fù)用，定義一個(gè)函數(shù)，其中包含布爾類型的lower參數(shù)，該參數(shù)為true時(shí)，則查找第一個(gè)大于等于target的下標(biāo)，該參數(shù)為false時(shí)，則查找第一個(gè)大于target的下標(biāo)
最后，因?yàn)閠arget可能不在數(shù)組中，因此需要重新校驗(yàn)兩個(gè)下標(biāo)leftIdx和rightIdx，看是否符合條件，如果符合，就返回[leftIdx,rightIdx]，不符合就返回[-1,-1]
class Solution {
public int[] searchRange(int[] nums, int target) {
//如果數(shù)組長度是0，則不用判斷
if (nums == null || nums.length == 0) {
return new int[]{-1, -1};
}
//如果target的值小于第一個(gè)元素或者大于最后一個(gè)元素，也不用判斷
if ((target < nums[0]) || (target > nums[nums.length - 1])) {
return new int[]{-1, -1};
}
int leftIdx = search(nums, target, true);
int rightIdx = search(nums, target, false) - 1;
if (leftIdx >= 0 && rightIdx < nums.length && leftIdx <= rightIdx && nums[leftIdx] == target && nums[rightIdx] == target) {
return new int[]{leftIdx, rightIdx};
}
return new int[]{-1, -1};
}
public int search(int[] nums, int target, boolean lower) {
int left = 0;
int right = nums.length - 1;
int mid;
int ans = nums.length;
while (left <= right) {
mid = left + ((right - left) >> 1);
//說明當(dāng)前的mid所在的值比target大，需要縮小范圍
//找leftIdx，如果target小于nums[mid]，縮小范圍
//如果target==nums[mid]，也要縮小范圍，但是會(huì)記錄mid
//找rightIdx，只要target<nums[mid]，縮小范圍
if (target < nums[mid] || (lower && target == nums[mid])) {
right = mid - 1;
ans = mid;
} else {
//找rightIdx，只要target < nums[mid] 不成立
//也就是target=nums[mid]或者target>nums[mid] left都會(huì)變化
left = mid + 1;
}
}
return ans;
}
}
（簡單，常見面試題）69. x的平方根
我的思路，將x的值賦給tmp，將tmp不斷除以2
記錄下面兩個(gè)數(shù)，在這兩個(gè)數(shù)之間使用二分查找：
- 使得tmp^2小于x的最大的tmp值
- 使得tmp^2大于x的最小的tmp值
class Solution {
public int mySqrt(int x) {
if (x == 0 || x == 1) {
return x;
}
int pre = x;
int tmp = x / 2;
while (tmp > x / tmp) { //原來是 tmp * tmp > x
pre = tmp;
tmp /= 2;
}
if (tmp == x / tmp) { //原來是 tmp * tmp == x
return tmp;
}
//pre和tmp之間找到答案，縮小范圍
return search(x, tmp, pre);
}
public int search(int x, int tmp, int pre) {
int left = tmp;
int right = pre;
int mid;
int ans = tmp;
while (left <= right) {
mid = left + ((right - left) >> 1);
if (mid == x / mid) { //原來是 mid * mid == x
return mid;
}
if (mid > x / mid) { // 原來是mid * mid > x
right = mid - 1;
} else {
ans = mid;
left = mid + 1;
}
}
return ans;
}
}
官網(wǎng)解答，筆記：
在不使用 x \sqrt{x} x?函數(shù)的情況下，得到x的平方根的整數(shù)部分。一般的思路有以下幾種：
- 通過其它的數(shù)學(xué)函數(shù)代替平方根函數(shù)得到精確結(jié)果，取整數(shù)部分作為答案
- 通過數(shù)學(xué)方法得到近似結(jié)果，直接作為答案
方法一 袖珍計(jì)算器算法
【袖珍計(jì)算器算法】是一種用指數(shù)函數(shù)exp和對數(shù)函數(shù)ln代替平方根函數(shù)的方法。通過有限的、可以使用的數(shù)學(xué)函數(shù)，得到想要的結(jié)果。
當(dāng)x=2147395600時(shí)，
e
1
2
ln
?
x
e^{\frac{1}{2}\ln x}
e21?lnx?的計(jì)算結(jié)果與正確值46340相差
1
0
?
11
10^{-11}
10?11，這樣在對結(jié)果取整數(shù)部分時(shí)，會(huì)得到46339這個(gè)錯(cuò)誤結(jié)果。
因此，在得到結(jié)果的整數(shù)部分ans后，應(yīng)該找出ans與ans+1中哪一個(gè)是真正的答案。
class Solution {
public int mySqrt(int x) {
if (x == 0 || x == 1) {
return x;
}
int ans = (int) Math.exp(0.5 * Math.log(x));
return (long) (ans + 1) * (ans + 1) > x ? ans : ans + 1;
}
}
方法二 二分查找
由于x平方根的整數(shù)部分ans是滿足 k 2 ≤ x k^2 \leq x k2≤x的最大k值，因此可以對k進(jìn)行二分查找，從而得到答案
二分查找的下界是1，上界可以粗略的=地設(shè)定為x。在二分查找中的每一步中，我們只需要比較中間元素mid的平方與x的大小關(guān)系，并通過比較的結(jié)果調(diào)整上下界的范圍。由于我們所有的運(yùn)算都是整數(shù)運(yùn)算，所以，不會(huì)存在誤差，因此在得到最終的答案ans后，也就不需要再去嘗試ans+1了。
class Solution {
public int mySqrt(int x) {
if (x == 0 || x == 1) {
return x;
}
int left = 1;
int right = x;
int mid;
int ans = -1;
while (left <= right) {
mid = left + ((right - left) >> 1);
if ((long) mid * mid == x) {
return mid;
}
if ((long) mid * mid < x) {
ans = mid;
left = mid + 1;
} else {
right = mid - 1;
}
}
return ans;
}
}
（簡單） 367. 有效的完全平方數(shù)
二分查找
class Solution {
public boolean isPerfectSquare(int num) {
if (num == 1) {
return true;
}
int left = 1;
int right = num;
int mid;
while (left <= right) {
mid = left + ((right - left) >> 1);
if ((long) mid * mid == num) {
return true;
}
if ((long) mid * mid < num) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return false;
}
}
當(dāng)然還可以使用內(nèi)置的庫函數(shù)
根據(jù)完全平方數(shù)的性質(zhì)，只需要判斷num的平方根x是否為整數(shù)即可。
class Solution {
public boolean isPerfectSquare(int num) {
int x = (int) Math.sqrt(num);
return x * x == num;
}
}
還有暴力法文章來源：http://www.zghlxwxcb.cn/news/detail-430917.html
如果num為完全平方數(shù)，那么一定存在正整數(shù)x滿足x * x = num。于是，可以從1開始遍歷所有的正整數(shù)，一直遍歷到46340即可，因?yàn)?span id="n5n3t3z" class="katex--inline"> 2 31 ? 1 ≈ 46340 \sqrt{2^{31}-1} \approx 46340 231?1?≈46340文章來源地址http://www.zghlxwxcb.cn/news/detail-430917.html
class Solution {
public boolean isPerfectSquare(int num) {
if (num == 1) {
return true;
}
for (int i = 2; i <= 46340; i++) {
if (i * i > num) {
break;
}
if (i * i == num) {
return true;
}
}
return false;
}
}
到了這里，關(guān)于代碼隨想錄 LeetCode數(shù)組篇 二分查找的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
