在排序數組中查找數字

在排序數組中查找數字

來自專欄基礎演算法筆記4 人贊了文章

在排序數組中查找數字

題目1：數字在排序數組中出現的次數

統計一個數字在排序數組中出現的次數。例如，輸入排序數組{1,2,3,3,3,3,4,5}和數字3，由於3出現了4次，因此輸出4.

思路：

2分查找數組中的第一個k：

1. 如果中間數字大於k，那麼k只可能出現在前半段

2. 如果中間數字小於k，那麼k只可能出現在後半段

3. 如果中間數字等於k：

- 如果中間數字的前面不是k，那麼中間數字恰好就是第一個k

- 如果中間數字的前面是k，那麼第一個k肯定在前半段

參考代碼：

root@gt:/home/git/Code# ./a.out 4root@gt:/home/git/Code# cat get1k.c #include <stdio.h>int get1k(int* pdata,int start,int end,int k){ if(start > end) return -1; int midIndex = start + (end - start)/2; int midData = pdata[midIndex]; if(midData > k) end = midIndex - 1; else if(midData < k) start = midIndex + 1; else { if((midIndex > 0 && pdata[midIndex - 1] != k) || midIndex == 0) return midIndex; else end = midIndex - 1; } return get1k(pdata,start,end,k);}int getknum(int* pdata,int len,int k){ if(pdata == NULL || len <= 0) return 0; int count = 0; int start = 0; int end = len - 1; int index = get1k(pdata,start,end,k); for(int i = index;i < len && pdata[i] == k;++i) ++count; return count;}int main(){ int pdata[] = {1,2,3,3,3,3,4,5}; int num = getknum(pdata,sizeof(pdata)/sizeof(int),3); printf("%d
",num); return 0;}

題目2：0～n-1中缺失的數字。

一個長度為n-1的遞增排序數組中的所有數字都是唯一的，並且每個數字都在範圍0~n-1之內。在範圍0～n-1內的n個數字中有且僅有一個數字不在該數組中，請找出這個數字。

思路：因為數組有序，因此數組中開始的一些數字與它們的下標相同。如果不在數組中的那個數字記為m，那麼所有比m小的數字下標都與它們的值相同。由於m不在數組中，m+1的下標正好是m。我們發現m正好是第一個值和下標不相等的下標。

1. 如果中間元素的值與下標相等，則查找右邊。

2. 如果中間元素的值與下標不相等，並且前面一個元素的下標與值正好相等，則這個下標就是數組中缺失的數字。

3. 如果中間元素的值與下標不相等，並且前面一個元素的下標與值也不相等，怎查找左邊。

參考代碼：

root@gt:/home/git/Code# ./a.out 6root@gt:/home/git/Code# cat getmiss.c #include <stdio.h>int getmiss(int* pdata,int len){ if(pdata == NULL || len <= 0) return -1; int start = 0; int end = len - 1; while(start <= end) { int mid = start + (end - start)/2; if(pdata[mid] == mid) start = mid + 1; else { if(pdata[mid -1] = mid - 1) return mid - 1; else end = mid - 1; } } return -1;}int main(){ int pdata[] = {0,1,2,3,4,5,6,8,9}; int res = getmiss(pdata,sizeof(pdata)/sizeof(int)); printf("%d
",res); return 0;}

題目3：數組中數值和下標相等的元素。

假設一個單調的數組裡的每一個元素都在整數並且是唯一的。實現一個函數，找出數組中任意一個數值等於其下標的元素。

思路：

1. 如果第i個數字的值大於下標i，那麼它右邊的數字都大於對應的下標，可以忽略。

2. 如果第i個數字的值小於下標i，那麼它左邊的數字都小於對應的下標，可以忽略。

3. 如果第i個數字的值等於下標i，則找到了。

參考代碼：

root@gt:/home/git/Code# ./a.out 3root@gt:/home/git/Code# cat getnum.c #include <stdio.h>int getnum(int* pdata,int len){ if(pdata == NULL || len <= 0) return -1; int start = 0; int end = len -1; while(start <= end) { int mid = start + (end - start)/2; if(pdata[mid] == mid) return mid; else { if(pdata[mid] > mid) end = mid - 1; else start = mid + 1; } } return -1;}int main(){ int pdata[] = {-3,-1,1,3,5}; int res = getnum(pdata,sizeof(pdata)/sizeof(int)); printf("%d
",res); return 0;}

推薦閱讀：