??鍵盤敲爛，年薪30萬??
目錄
普通版本的二分查找：
right只負(fù)責(zé)控制邊界(少了兩次比較)：
時(shí)間復(fù)雜度更穩(wěn)定的版本：
BSLeftmost：
BSRightmost：文章來源：http://www.zghlxwxcb.cn/news/detail-752849.html
?文章來源地址http://www.zghlxwxcb.cn/news/detail-752849.html
普通版本的二分查找：
- ??細(xì)節(jié)1：循環(huán)判定條件是left <= right
- ?細(xì)節(jié)2：mid = (left + right ) >>> 1 原因見代碼注釋
/***
* 二分查找的實(shí)現(xiàn) 3個版本
* 時(shí)間復(fù)雜度：O（longn）
* 空間復(fù)雜度：O（1）
*
* 細(xì)節(jié)1：循環(huán)判定條件是left <= right
* 細(xì)節(jié)2：mid計(jì)算要用 >>> 因?yàn)閘eft + right 可能越界
* 例如：right = Integer.MAX_INT-1 left = 0;
* 第一輪計(jì)算沒問題 假設(shè)mid < target
* left = mid + 1; 這是后left+ right 就超出int的最大范圍，變成負(fù)數(shù)
* 原因很簡單：java沒有無符號數(shù)，最高位表示符號位，/ 運(yùn)算是先將補(bǔ)碼轉(zhuǎn)原碼 >>>位運(yùn)算是直接再二進(jìn)制上運(yùn)算
*/
public class Demo1 {
public static void main(String[] args) {
int[] nums = {1,4,6,8,15,76,145};
int target = 145;
int index1 = method1(nums, target);
System.out.println(target + "索引為" + index1);
System.out.println(target + "索引為" + index2);
}
private static int method1(int[] nums, int target) {
int left = 0, right = nums.length-1;
while(left <= right){
//細(xì)節(jié) 用無符號右移運(yùn)算符
int mid = (left + right) >>> 1;
if(nums[mid] > target){
right = mid - 1;
}else if (nums[mid] < target){
left = mid + 1;
}else{
return mid;
}
}
return -1;
}
}
right只負(fù)責(zé)控制邊界(少了兩次比較)：
- 改動1：while條件是left < right
- 改動2：right = nums.length
public class Demo1 {
public static void main(String[] args) {
int[] nums = {1,4,6,8,15,76,145};
int target = 145;
int index2 = method2(nums, target);
System.out.println(target + "索引為" + index2);
}
}
private static int method2(int[] nums, int target) {
int left = 0, right = nums.length; //right 只代表有邊界，不參與比較
while(left < right){
int mid = (left + right) >>> 1;
if(nums[mid] < target){
left = mid + 1;
}else if(nums[mid] > target){
right = mid;
}else {
return mid;
}
}
return -1;
}
時(shí)間復(fù)雜度更穩(wěn)定的版本：
- 細(xì)節(jié)：減少了if比較次數(shù)
public class Demo1 {
public static void main(String[] args) {
int[] nums = {1,4,6,8,15,76,145};
int target = 145;
int index3 = method3(nums, target);
System.out.println(target + "索引為" + index3);
}
}
private static int method3(int[] nums, int target) {
//這個最牛逼
//減少循環(huán)內(nèi)的比較次數(shù)
int left = 0, right = nums.length;
while(1 < right - left){
int mid = (left + right) >>> 1;
if(nums[mid] > target){
right = mid;
}else{
left = mid;
}
}
if(nums[left] == target){
return left;
}
return -1;
}
BSLeftmost：
/**
*
* 應(yīng)用：求成績排名 求前任
*/
public class Leftmost {
public static void main(String[] args) {
int[] nums = {1,2,4,4,4,6,7};
int target = 3;
/***
* params
* return 找到了 - 返回靠左的下標(biāo)
* 沒找到 - 返回>target的最靠左下標(biāo)
*/
int ans = BSLeftmost(nums, target);
System.out.println(ans);
}
private static int BSLeftmost(int[] nums, int target) {
int left = 0, right = nums.length -1;
while(left <= right){
int mid = (left+right) >>> 1;
if(target > nums[mid]){
left = mid + 1;
} else{
right = mid - 1;
}
}
return left;
}
}
BSRightmost：
/**
*
* 求后任
*/
public class Rightmost {
public static void main(String[] args) {
int[] nums = {1,2,4,4,4,6,7};
int target = 3;
/**
* return 找到了返回下標(biāo)
* 沒找到返回 <= targer的最靠右索引
*
*/
int ans = BSRightmost(nums, target);
System.out.println(ans);
}
private static int BSRightmost(int[] nums, int target) {
int left = 0, right = nums.length-1;
while(left <= right){
int mid = (left + right) >>> 1;
if(target >= nums[mid]){
left = mid + 1;
}else {
right = mid - 1;
}
}
return left - 1;
}
}
到了這里，關(guān)于【手撕數(shù)據(jù)結(jié)構(gòu)】二分查找(好多細(xì)節(jié))的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
