題目來源
劍指 Offer 53 - I. 在排序數(shù)組中查找數(shù)字 I
二分查找
初始化： 左邊界 i=0 ，右邊界 j=nums.length?1。
循環(huán)二分： 當(dāng)閉區(qū)間 [i, j] 無元素時跳出；
- 計(jì)算中點(diǎn) m=(i+j)/2 （向下取整）；
- 若 nums[m]<target，則 target 在閉區(qū)間 [m+1,j] 中，因此執(zhí)行 i=m+1；
- 若 nums[m]>target，則 target 在閉區(qū)間 [i,m?1] 中，因此執(zhí)行 j=m?1；
- 若 nums[m]=target，則右邊界 right 在閉區(qū)間 [m+1,j] 中；左邊界 left 在閉區(qū)間 [i,m?1] 中。因此分為以下兩種情況：
- 若查找 右邊界 right ，則執(zhí)行 i=m+1；（跳出時 i 指向右邊界）
- 若查找 左邊界 left ，則執(zhí)行 j=m?1；（跳出時 j 指向左邊界）
返回值： 應(yīng)用兩次二分，分別查找 right 和 left ，最終返回 right?left?1 即可。
求比target大的值
while(left <= right){
int mid = left + ((right-left)>>1);
if(nums[mid] <= target){
left = mid + 1;
}else{
right = mid - 1;
}
}
求比taget小的值
while(left <= right){
int mid = left + ((right-left)>>1);
if(nums[mid] < target){
left = mid + 1;
}else{
right = mid - 1;
}
}
最終直接l-r-1即可，完整代碼文章來源：http://www.zghlxwxcb.cn/news/detail-427595.html
class Solution {
public int search(int[] nums, int target) {
int left = 0;
int right = nums.length-1;
while(left <= right){
int mid = left + ((right-left)>>1);
if(nums[mid] <= target){
left = mid + 1;
}else{
right = mid - 1;
}
}
int r = left;
if(right >= 0 && nums[right] != target) return 0;
left = 0;
right = nums.length-1;
while(left <= right){
int mid = left + ((right-left)>>1);
if(nums[mid] < target){
left = mid + 1;
}else{
right = mid - 1;
}
}
int l = right;
return r - l - 1;
}
}
文章來源地址http://www.zghlxwxcb.cn/news/detail-427595.html
到了這里，關(guān)于劍指 Offer 53 - I. 在排序數(shù)組中查找數(shù)字 I的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
