在排序数组中查找数字
原创在排序数组中查找数字
原创
在排序数组中查找数字
题目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
4
root@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\n",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
6
root@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\n",res);
return 0;
}题目3：数组中数值和下标相等的元素。 假设一个单调的数组里的每一个元素都在整数并且是唯一的。实现一个函数，找出数组中任意一个数值等于其下标的元素。
思路： 1. 如果第i个数字的值大于下标i，那么它右边的数字都大于对应的下标，可以忽略。 2. 如果第i个数字的值小于下标i，那么它左边的数字都小于对应的下标，可以忽略。 3. 如果第i个数字的值等于下标i，则找到了。
参考代码：
root@gt:/home/git/Code# ./a.out
3
root@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\n",res);
return 0;
}原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
腾讯云开发者
