二分查找問(wèn)題全集

二分查找問(wèn)題全集1，原始二分查找題目：給定一個(gè)有序（非降序）數(shù)組A，求任意一個(gè)i使得A[i]等于target，不存在則返回-1例如：[2,4,6,8,9]找(4)位置11.1遞歸版[cpp]\o"viewplain"viewplain\o"copy"copy\o"print"print\o"?"?int

bSearch(int

a[],

int

low,

int

high,

int

target){

if(low

>

high)

return

-1;

int

mid

=

(low

+

high)/2;

if(target<a[mid])

return

bSearch(a,low,mid-1,target);

else

if(target>a[mid])

return

bSearch(a,mid+1,high,target);

//if(target

==

a[mid])

return

mid;

}

1.2迭代版[cpp]\o"viewplain"viewplain\o"copy"copy\o"print"print\o"?"?int

search(int

A[],

int

n,

int

target)

{

int

low

=

0,

high

=

n-1;

while(low

<=

high)

{

//

注意：若使用(low+high)/2求中間位置容易溢出

int

mid

=

low+((high-low)>>1);

if(A[mid]

==

target)

return

mid;

else

if(A[mid]

<

target)

low

=

mid+1;

else

//

A[mid]

>

target

high

=

mid-1;

}

return

-1;

}

1.3返回插入位置給定一個(gè)有序（非降序）數(shù)組A，若target在數(shù)組中出現(xiàn)，返回位置，若不存在，返回它應(yīng)該插入的位置。[cpp]\o"viewplain"viewplain\o"copy"copy\o"print"print\o"?"?int

search(int

A[],

int

n,

int

target)

{

int

low

=

0,

high

=

n-1;

while(low

<=

high)

{

//

注意：若使用(low+high)/2求中間位置容易溢出

int

mid

=

low+((high-low)>>1);

if(A[mid]

==

target)

return

mid;

else

if(A[mid]

<

target)

low

=

mid+1;

else

//

A[mid]

>

target

high

=

mid-1;

}

return

-(low+1);

}

之所以返回-（low+1）而不是直接返回-low是因?yàn)閘ow可能為0，如果直接返回-low就無(wú)法判斷是正常返回位置0還是查找不成功返回的0。2，含重復(fù)元素，求=target的最小一個(gè)問(wèn)題：給定一個(gè)有序（非降序）數(shù)組A，可含有重復(fù)元素，求最小的i使得A[i]等于target，不存在則返回-1例如：A[2,4,6,8,8,8,9]求8得最小位置3[cpp]\o"viewplain"viewplain\o"copy"copy\o"print"print\o"?"?int

search(int

A[],

int

n,

int

target)

{

int

low

=

0,

high

=

n-1;

while(low

<=

high)

{

//

注意：若使用(low+high)/2求中間位置容易溢出

int

mid

=

low+((high-low)>>1);

if(A[mid]

==

target)

{

if(mid

>

0

&&

A[mid-1]

==

target)

high

=

mid-1;

else

return

mid;

}

else

if(A[mid]

<

target)

low

=

mid+1;

else

//

A[mid]

>

target

high

=

mid-1;

}

return

-(low+1);

}

3，含重復(fù)元素，求=target的最大一個(gè)問(wèn)題：給定一個(gè)有序（非降序）數(shù)組A，可含有重復(fù)元素，求最大的i使得A[i]等于target，不存在則返回-1例如：A[2,4,6,8,8,8,9]求8得最大位置5[cpp]\o"viewplain"viewplain\o"copy"copy\o"print"print\o"?"?int

search(int

A[],

int

n,

int

target)

{

int

low

=

0,

high

=

n-1;

while(low

<=

high)

{

//

注意：若使用(low+high)/2求中間位置容易溢出

int

mid

=

low+((high-low)>>1);

if(A[mid]

==

target)

{

if(mid

<

n-1

&&

A[mid+1]

==

target)

low

=

mid+1;

else

return

mid;

}

else

if(A[mid]

<

target)

low

=

mid+1;

else

//

A[mid]

>

target

high

=

mid-1;

}

return

-(low+1);

}

4，含重復(fù)元素，求<target的最大一個(gè)問(wèn)題：給定一個(gè)有序（非降序）數(shù)組A，可含有重復(fù)元素，求最大的i使得A[i]小于target，不存在則返回-1

例如：A[2,4,6,8,8,8,9]求9得最大位置5問(wèn)題轉(zhuǎn)化：含重復(fù)元素，求2【=target的最小一個(gè)】的前一個(gè)。[cpp]\o"viewplain"viewplain\o"copy"copy\o"print"print\o"?"?int

search(int

A[],

int

n,

int

target)

{

int

low

=

0,

high

=

n-1;

while(low

<=

high)

{

//

注意：若使用(low+high)/2求中間位置容易溢出

int

mid

=

low+((high-low)>>1);

if(A[mid]

==

target)

{

if(mid

>

0

&&

A[mid-1]

==

target)

high

=

mid-1;

else

return

(mid==0)?-1:mid-1;

}

else

if(A[mid]

<

target)

low

=

mid+1;

else

//

A[mid]

>

target

high

=

mid-1;

}

return

-(low+1);

}

5，含重復(fù)元素，求>target的最小一個(gè)問(wèn)題：給定一個(gè)有序（非降序）數(shù)組A，可含有重復(fù)元素，求最小的i使得A[i]大于target，不存在則返回-1例如：A[2,4,6,8,8,8,9]求6的最小位置3問(wèn)題轉(zhuǎn)化：含重復(fù)元素，求3【=target的最大一個(gè)】的后一個(gè)。[cpp]\o"viewplain"viewplain\o"copy"copy\o"print"print\o"?"?int

search(int

A[],

int

n,

int

target)

{

int

low

=

0,

high

=

n-1;

while(low

<=

high)

{

//

注意：若使用(low+high)/2求中間位置容易溢出

int

mid

=

low+((high-low)>>1);

if(A[mid]

==

target)

{

if(mid

<

n-1

&&

A[mid+1]

==

target)

low

=

mid+1;

else

return

(mid==n-1)?-n:mid+1;

}

else

if(A[mid]

<

target)

low

=

mid+1;

else

//

A[mid]

>

target

high

=

mid-1;

}

return

-(low+1);

}

6，含重復(fù)元素，求=target的出現(xiàn)次數(shù)問(wèn)題：給定一個(gè)有序（非降序）數(shù)組A，可含有重復(fù)元素，求target在數(shù)組中出現(xiàn)的次數(shù)。例如：A[2,4,6,8,8,8,9]求8的出現(xiàn)次數(shù)3求出第一次出現(xiàn)位置和最后一次出現(xiàn)位置。由于前面都已實(shí)現(xiàn)，這里不多解釋。請(qǐng)參考實(shí)現(xiàn)代碼與注釋[cpp]\o"viewplain"viewplain\o"copy"copy\o"print"print\o"?"?int

count(int

A[],

int

n,

int

target)

{

int

firstPos

=

searchFirstPos(A,

n,

target);

//

第一次出現(xiàn)位置

if(firstPos

==

-1)

return

0;

int

lastPos

=

searchLastPos(A,

n,

target);

//

最后一次出現(xiàn)位置

return

lastPos-firstPos+1;

//

出現(xiàn)次數(shù)

}

7，含重復(fù)元素，求絕對(duì)值最小的元素問(wèn)題：給定一個(gè)有序（非降序）數(shù)組A，可含有重復(fù)元素，求絕對(duì)值最小的元素的位置例如：A[-4,-2,-1,2,3,8,9]求結(jié)果為2[cpp]\o"viewplain"viewplain\o"copy"copy\o"print"print\o"?"?int

searchMinAbs(int

A[],

int

n)

{

int

low

=

0,

high

=

n-1;

while(low

<

high)

{

int

mid

=

low+((high-low)>>1);

if(A[mid]

<

0)

low

=

mid+1;

else

//

A[mid]

>=

0

high

=

mid;

}

/*

循環(huán)結(jié)束時(shí)，如果low

!=

n-1，A[low]

>=

0，如果low>0，A[low-1]

<

0

*/

if(low

>

0

&&

abs(A[low-1])

<

abs(A[low]))

return

low-1;

else

return

low;

}

8，問(wèn)題：給定一個(gè)有序（非降序）數(shù)組A和一個(gè)有序（非降序）數(shù)組B，可含有重復(fù)元素，求兩個(gè)數(shù)組合并結(jié)果中的第k(k>=0)個(gè)數(shù)字。

這個(gè)題目出現(xiàn)了兩個(gè)數(shù)組，有序的，不管怎樣我們就應(yīng)該首先考慮二分查找是否可行。若使用順序查找，時(shí)間復(fù)雜度最低為O(k)，就是類(lèi)似歸并排序中的歸并過(guò)程。使用用二分查找時(shí)間復(fù)雜度為O(logM+logN)。二分查找的具體實(shí)現(xiàn)過(guò)程請(qǐng)參考實(shí)現(xiàn)代碼與注釋。[cpp]\o"viewplain"viewplain\o"copy"copy\o"print"print\o"?"?int

findKthIn2SortedArrays(int

A[],

int

m,

int

B[],

int

n,

int

k)

{

if(m

<=

0)

//

數(shù)組A中沒(méi)有元素，直接在B中找第k個(gè)元素

return

B[k];

if(n

<=

0)

//

數(shù)組B中沒(méi)有元素，直接在A中找第k個(gè)元素

return

A[k];

int

i

=

(m-1)>>1;

//

數(shù)組A的中間位置

int

j

=

(n-1)>>1;

//

數(shù)組B的中間位置

if(A[i]

<=

B[j])

//

數(shù)組A的中間元素小于等于數(shù)組B的中間元素

{

/*

設(shè)x為數(shù)組A和數(shù)組B中小于B[j]的元素?cái)?shù)目，則i+1+j+1小于等于x，

因?yàn)锳[i+1]到A[m-1]中還可能存在小于等于B[j]的元素；

如果k小于i+1+j+1，那么要查找的第k個(gè)元素肯定小于等于B[j]，

因?yàn)閤大于等于i+1+j+1；既然第k個(gè)元素小于等于B[j]，那么只

需要在A[0]~A[m-1]和B[0]~B[j]中查找第k個(gè)元素即可，遞歸調(diào)用下去。

*/

if(k

<

i+1+j+1)

{

if(j

>

0)

return

findKthIn2SortedArrays(A,

m,

B,

j+1,

k);

else

//

j

==

0時(shí)特殊處理，防止死循環(huán)

{

if(k

==

0)

return

min(A[0],

B[0]);

if(k

==

m)

return

max(A[m-1],

B[0]);

return

A[k]

<

B[0]

?

A[k]

:

max(A[k-1],

B[0]);

}

}

/*

設(shè)y為數(shù)組A和數(shù)組B中小于于等于A[i]的元素?cái)?shù)目，則i+1+j+1大于等于y；

如果k大于等于i+1+j+1，那么要查找到第k個(gè)元素肯定大于A[i]，因?yàn)?/p>

i+1+j+1大于等于y；既然第k個(gè)元素大于A[i]，那么只需要在A[i+1]~A[m-1]

和B[0]~B[n-1]中查找第k-i-1個(gè)元素，遞歸調(diào)用下去。

*/

else

return

findKthIn2SortedArrays(A+i+1,

m-i-1,

B,

n,

k-i-1);

}

//

如果數(shù)組A的中間元素大于數(shù)組B的中間元素，那么交換數(shù)組A和B，重新調(diào)用即可

else

return

findKthIn2SortedArrays(B,

n,

A,

m,

k);

}

9問(wèn)題：

一個(gè)有序（升序）數(shù)組，沒(méi)有重復(fù)元素，在某一個(gè)位置發(fā)生了旋轉(zhuǎn)后，求target在變化后的數(shù)組中出現(xiàn)的位置，不存在則返回-1如0124567可能變成4567012

我們先比較中間元素是否是目標(biāo)值，如果是返回位置。如果不是，我們就應(yīng)該想辦法將搜索區(qū)間減少一半。因?yàn)榇嬖谛D(zhuǎn)變化，所以我們要多做一些判斷。我們知道因?yàn)橹挥幸淮涡D(zhuǎn)變化，所以中間元素兩邊的子數(shù)組肯定有一個(gè)是有序的，那么我們可以判斷target是不是在這個(gè)有序的子數(shù)組中，從而決定是搜索這個(gè)子數(shù)組還是搜索另一個(gè)子數(shù)組。具體請(qǐng)參考實(shí)現(xiàn)代碼與注釋。[cpp]\o"viewplain"viewplain\o"copy"copy\o"print"print\o"?"?int

searchInRotatedArray(int

A[],

int

n,

int

target)

{

int

low

=

0,

high

=

n-1;

while(low

<=

high)

{

int

mid

=

low+((high-low)>>1);

if(A[mid]

==

target)

return

mid;

if(A[mid]

>=

A[low])

{

//

low

~

mid

是升序的

if(target

>=

A[low]

&&

target

<

A[mid])

high

=

mid-1;

else

low

=

mid+1;

}

else

{

//

mid

~

high

是升序的

if(target

>

A[mid]

&&

target

<=

A[high])

low

=

mid+1;

else

high

=

mid-1;

}

}

return

-1;

}

如果這樣的數(shù)組中存在重復(fù)元素，還能使用二分嗎？答案是不能。請(qǐng)看幾個(gè)例子

[1,2,2,2,2],[2,1,2,2,2],[2,2,1,2,2],[2,2,2,1,2],[2,2,2,2,1]這些都是有第一個(gè)數(shù)組旋轉(zhuǎn)一次變化來(lái)的，我們不能通過(guò)二分確定是否存在元素1.10，問(wèn)題：一個(gè)有序（升序）數(shù)組，沒(méi)有重復(fù)元素，在某一個(gè)位置發(fā)生了旋轉(zhuǎn)后，求最小值所在位置如果中間元素小于左端元素，則最小值在左半?yún)^(qū)間內(nèi)（包含中間元素）；如果中間元素大于右端元素，則最小值在右半?yún)^(qū)間內(nèi)（包含中間元素）。請(qǐng)參考實(shí)現(xiàn)代碼與注釋。[cpp]\o"viewplain"viewplain\o"copy"copy\o"print"print\o"?"?int

searchMinInRotatedArray(int

A[],

int

n)

{

if(n

==

1)

return

0;

int

low

=

0,

high

=

n-1;

while(low

<

high-1)

//

保證mid

!=

low且mid

!=

high

{

int

mid

=

low+((high-low)>>1);

if(A[mid]

<

A[low])

//

最小值在low~mid

high

=

mid;

else

//

A[mid]

>

A[low],

//

最小值在mid和high之間

low

=

mid;

}

return

A[low]

<

A[low+1]

?

low

:

low+1;

}

11,問(wèn)題：

一個(gè)有序（升序）數(shù)組，沒(méi)有重復(fù)元素，在某一個(gè)位置發(fā)生了旋轉(zhuǎn)后，求第k(k>0)小元素的位置

我們可以利用上一題的解答，求出最小值所在位置后，便可以求出第k小元素。請(qǐng)參考實(shí)現(xiàn)代碼與注釋[cpp]\o"viewplain"viewplain\o"copy"copy\o"print"print\o"?"?int

searchKthInRotatedArray(int

A[],

int

n,

int

k)

{

int

posMin

=

searchMinInRotatedArray(A,

n);

return

(posMin+k-1)%n;

}

12，查找旋轉(zhuǎn)數(shù)組的最小數(shù)字題目：即找分界點(diǎn)，比如34512，返回的是位置3。以題目中的旋轉(zhuǎn)數(shù)組為例，{3,4,5,1,2}，我們可以有序數(shù)組經(jīng)過(guò)旋轉(zhuǎn)以后被分割為兩段有序的數(shù)組，比如此處被分為{3,4,5}{1,2}這樣連個(gè)數(shù)組，并且前半段數(shù)組中的數(shù)字肯定大于等于后半段的數(shù)組。我們找中間元素a[mid]，讓其跟元素首元素a[low]和尾元素a[high]比較，如果大于首元素a[low]，則中間元素屬于前半段有序數(shù)組；如果小于尾元素a[high]，那么中間元素就是后半段的元素。這里我們?cè)O(shè)定兩個(gè)指針start和end分別指向數(shù)組的首尾元素，然后當(dāng)start指向前半段最后一個(gè)元素，end指向后半段第一個(gè)元素，這是程序就找到了數(shù)組中的最小元素，就是end指向的那個(gè)數(shù)，程序的出口就是end-start==1。[cpp]\o"viewplain"viewplain\o"copy"copy\o"print"print\o"?"?int

bSearchMinValue(int

a[],

int

low,

int

high){

//終止遞歸條件是low和high差1，原因是后面mid都不是+1-1處理的

if(low+1==high)

return

high;

int

mid

=

(low

+

high)/2;

if(a[mid]>a[low])//左側(cè)有序，在右邊找分界點(diǎn)

return

bSearchMinValue(a,mid,high);

if(a[mid]<a[high])//右側(cè)有序，在左邊找分界點(diǎn)

return