利用快速排序和二分查找数字出现次数

 

 

#include <windows.h>
#include <stdlib.h> 
#include <stdio.h> 
#include <time.h>
#include <ctime>
#include <algorithm> 
#define ARRLEN 1000
using namespace std;
 
int arr[ARRLEN];
 
int Patition(int arr3[], int low, int high)
{
 
	int pivotkey=arr3[low];
	int temp = arr3[low];
 
	while(low<high)
	{
 
		while(low <high && arr3[high]>=pivotkey)
		{
			--high;;
		}
		arr3[low]=arr3[high];
		while(low<high && arr3[low]<=pivotkey)
		{
			++low;;
		}
		arr3[high]=arr3[low];
	}
	arr3[low] = temp;
	return low;
 
}
void QuickSort(int arr3[], int low, int high)
{
	if(low<high)
	{
		int pivotloc=Patition(arr3,low, high);
		QuickSort(arr3, low, pivotloc-1);
		QuickSort(arr3, pivotloc+1, high);
	}
}
int BinarySearch(int arr[],int start,int end,int key){
	if (arr[start]==key)
		return start;
	if (arr[end]==key)
		return end;
 
	while(start<end){
		int mid=(start+end)/2;
		if (arr[mid]==key){
			return mid;
		}
		if (arr[mid]>key)
			end=mid-1;
		else
			start=mid+1;
	}
	if(start>=end)
		return -1;
}
int SearchTheTimesOfK(int arr[],int start,int end,int key){
	int index=BinarySearch(arr,0,ARRLEN-1,key);
	if(index==-1)return index;
 
	int firstindex=index,lastindex=index;
	while (firstindex>=0&&arr[firstindex]==key)
		firstindex--;
	while(lastindex<ARRLEN&&arr[lastindex]==key)
		lastindex++;
 
	return lastindex-firstindex-1;
}
void InitArr(){
	for (int i=0,j;i<ARRLEN;i++)
	{
		j=rand()%1000;
		arr[i]=j;
	}
}
void Display(int arr[],int n){
	int i=0;
	while(n--){
		printf("%d ",arr[i]);
		i++;
	}
}
int main(void){
	InitArr();
	QuickSort(arr,0,ARRLEN-1);
	Display(arr,ARRLEN);
	printf("\n");
	int times=SearchTheTimesOfK(arr,0,ARRLEN-1,999);
	if (times!=-1)
	   printf("%d",times);
	else
		printf("找不到！");
	getchar();
	return 0;
}