|
|
首先說明一下這個問題中提到的"有序序列"的概念.它指的是其中的元素在序列長度范圍之內,而且是有序(比如升序)排列的序列.比如一個只包含10個元素的數組, 其中的元素大小在[0, 9]之間,而且是升序排列的. 這兩個問題是二分查找算法的典型應用. 首先來看看查找不存在元素的算法.假設一個元素x不存在, 那么在序列中, 在x位置的元素是x + 1, 以此類推.
初始化 left = 0, right = len - 1 (其中len是這個有序序列的長度, 假設序列從0開始)
當left <= right時繼續循環:
pos = (left + right) / 2
如果 序列的第pos個元素不等于pos
那么不存在的元素一定出現在pos之前, 將right = pos - 1
否則
pos之前的元素都是存在的, 因此 left = pos + 1
根據上面的查找原則, 在left之前的元素都是存在的, 返回left
再來看看查找重復元素的算法.假設一個元素x重復出現, 那么在序列中, 在x + 1位置的元素是x, 而x+1出現在序列的x+2位置上, 以此類推. 從上面的算法可以看出, 最后返回的位置, 在它之前的元素位置都是正確的, 就是說,出現在了它們應該出現的位置, 因此, 上面算法也依然可以用于這個問題上面, 只要把上面算法的返回值 - 1即可以得到本算法要求的返回值. 關于這個問題,我之前有過類似問題的討論: 1) 二分查找算法(迭代和遞歸版本)2) 求出不在里面的數來這個問題的討論也是對<<編程珠璣>>第二章第一個算法問題的補充. C代碼如下:
/*
* 查找有序序列中 重復/不存在 的數算法演示
* 版權所有:http://www.shnenglu.com/converse/
*/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define FUNC_IN() printf("\nin %s \n\n", __FUNCTION__)
#define FUNC_OUT() printf("\nout %s\n\n", __FUNCTION__)
/* 生成一個長度為len的數組, 其中array[i] = i(0<=i<len) */
void generate_array(int array[], int len);
/* 向長度為len的有序數組中新增一個元素x(0<=x<len - 1), 同時保持原有數組有序 */
void add_to_array(int array[], int len, int x);
/* 刪除長度為len的有序數組中的一個元素x(0<=x<len), 同時保存原有數組有序 */
void del_from_array(int array[], int len, int x);
/* 打印一個數組 */
void display_array(int array[], int len);
/* 查找一個長度為len的有序數組中哪個元素不存在 */
int find_not_exist(int array[], int len);
/* 查找一個長度為len的有序數組中哪個元素重復了 */
int find_duplicate(int array[], int len);
int main(int argc, char *argv[])
{
int count = 10;
int *array = NULL;
srand(time(NULL));
if (argc == 2)
{
count = atoi(argv[1]);
}
/* 申請內存的時候多申請一個元素 */
if ((array = (int *)malloc((count + 1) * sizeof(int))) == NULL)
{
printf("malloc error!\n");
exit(-1);
}
/* 首先生成一個元素都是有序的整型數組 */
generate_array(array, count);
display_array(array, count);
/* 刪除其中的一個元素 */
del_from_array(array, count, rand() % count);
display_array(array, count);
/* 查找不存在的元素 */
int x = find_not_exist(array, count);
printf("the element not exist is %d\n", x);
/* 把刪除的元素補上 */
add_to_array(array, count + 1, x);
/* 新增一個重復的元素 */
add_to_array(array, count + 1, rand() % count);
display_array(array, count + 1);
/* 查找重復的元素 */
printf("the element duplicate is %d\n", find_duplicate(array, count + 1));
free(array);
return 0;
}
void generate_array(int array[], int len)
{
int i;
for (i = 0; i < len; ++i)
{
array[i] = i;
}
}
void add_to_array(int array[], int len, int x)
{
int i;
/* 把[x + 1, len - 1]之間的元素右移一個位置 */
for (i = x + 1; i < len - 1; ++i)
{
array[i + 1] = i;
}
/* x + 1的位置保存重復的x, 這樣數組仍然是有序的 */
array[x + 1] = x;
}
void del_from_array(int array[], int len, int x)
{
int i;
/* 將[x, len)的元素向左移動一個位置 */
for (i = x; i < len; ++i)
{
array[i] = i + 1;
}
printf("del_from_array element is %d\n", x);
}
void display_array(int array[], int len)
{
int i;
printf("\n{ ");
for (i = 0; i < len; ++i)
{
printf("%d ", array[i]);
}
printf("}\n");
}
int find_not_exist(int array[], int len)
{
FUNC_IN();
int left, right, pos, count;
for (left = 0, right = len - 1, count = 1; left <= right; count++)
{
pos = (left + right) / 2;
printf("[%d] left = %d, pos = %d, right = %d\n", count, left, pos, right);
/*
* 如果array[pos] != pos, 那么不存在的元素一定在[left, pos - 1]之間
*/
if (array[pos] != pos)
{
right = pos - 1;
}
else
{
left = pos + 1;
}
}
FUNC_OUT();
/* left之前的元素都是存在的 */
return left;
}
int find_duplicate(int array[], int len)
{
/*
* find_not_exist()函數的返回值表示在它之前的元素都是正確的,
* 因此這個返回位置就是有重復的元素位置 + 1, 于是要減去1
* */
return find_not_exist(array, len) - 1;
}
|