// Determine whether a contains value k
bool BinarySearch(int *a, int n, int k)
{
int left = 0 ;
int right = n - 1 ;
while (left <= right)
{
int mid = (left + right) ;
if(a[mid] < k)
left = mid + 1 ;
if(a[mid] == k)
return true ;
else
right = mid - 1 ;
}
return false ;
}
// Compare function for qsort
int compare(const void* a, const void* b)
{
return *(int*)a - *(int*)b ;
}
总结一下，对于在数组中进行查找的问题，可以分如下两种情况处理：
如果给定的数组有序，那么首先应该想到Binary Search，所需O(logn)。
如果给定的数组无序，那么首先应该想到对数组进行排序，很多排序算法都能在O(nlogn)时间内对数组进行排序，然后再使用二分搜索，总的时间复杂度仍是O(nlogn)。
如果能做到以上两点，大多数关于数组的查找问题，都能迎刃而解。
找出数组中唯一的重复元素
给定含有1001个元素的数组，其中存放了1-1000之内的整数，只有一个整数是重复的，请找出这个数。
求出整个数组的和，再减去1-1000的和即可，代码略。
找出出现奇数次的元素
给定一个含有n个元素的整型数组a，其中只有一个元素出现奇数次，找出这个元素。
因为对于任意一个数k，有k ^ k = 0，k ^ 0 = k，所以将a中所有元素进行异或，那么个数为偶数的元素异或后都变成了0，只留下了个数为奇数的那个元素。
int FindElementWithOddCount(int *a, int n)
{
int r = a[0] ;
for (int i = 1; i
求数组中满足给定和的数对
给定两个有序整型数组a和b，各有n个元素，求两个数组中满足给定和的数对，即对a中元素i和b中元素j，满足i + j = d(d已知)。
两个指针i和j分别指向数组的首尾，然后从两端同时向中间遍历，直到两个指针交叉。
// 找出满足给定和的数对
void FixedSum(int* a, int* b, int n, int d)
{
for (int i = 0, j = n - 1; i < n && j >= 0)
{
if (a[i] + b[j] < d)
++i ;
else if (a[i] + b[j] == d)
{
cout << a[i] << ", " << b[j] << endl ;
++i ;
--j ;
}
else // a[i] + b[j] > d
--j ;
}
}
最大子段和
给定一个整型数组a，求出最大连续子段之和，如果和为负数，则按0计算，比如1， 2， -5， 6， 8则输出6 + 8 = 14。
编程珠玑上的经典题目，不多说了。
// 子数组的最大和
int Sum(int* a, int n)
{
int curSum = 0;
int maxSum = 0;
for (int i = 0; i < n; i++)
{
if (curSum + a[i] < 0)
curSum = 0;
else
{
curSum += a[i] ;
maxSum = max(maxSum, curSum);
}
}
return maxSum;
}
最大子段积
给定一个整型数足a，求出最大连续子段的乘积，比如 1， 2， -8， 12， 7则输出12 * 7 = 84。
