查找

顺序查找

int sequenceSearch(int a[], int count, int targetValue) {
    if (!a || count <=0) return -1;

    for (int i=0; i<count; i++) {
        if (targetValue == a[i]) return i;
    } 
    
    return -1;
}

二分查找

int binarySearch(int a[], int count, int targetValue) {
    
    if (!a || count<=0) return -1;

    return iterativeBinarySearch(a, count, targetValue);
    //return recursiveBinarySearch(a, targetValue, 0, count - 1);
}

int recursiveBinarySearch(int a[], int targetValue, int low, int high) {
    int middleIndex = 0    

    if (!a || low > high) return -1;
    
    middleIndex = low + (hight-low) / 2;
    if (a[middleIndex] == targetValue) return middleIndex;
    else if (a[middleIndex] < targetValue) 
        return recursiveBinarySearch(a, targetValue, middleIndex+1, hight);
    else return recursiveBinarySearch(a, targetValue, low, middleIndex-1);
}

int iterativeBinarySearch(int a[], int count, int targetValue) {
    int middleIndex = 0;
    int row = 0, high = count - 1;
    
    if (!a || count <= 0) return -1;

    while (row <= high) {
        middleIndex = low + (high - low) / 2;
        if (a[middleIndex] == targetValue) return middleIndex;
        else if (a[middleIndex] < targetValue) low = middleIndex + 1;
        else high = middleIndex - 1;
    }

    return -1;
}

插值查找

int insertSearch(int a[], int count, int targetValue) {
  return recursiveInsertSearch(a,  targetValue, 0, count - 1);
}

int recursiveInsertSearch(int a[], int targetValue, int low, int high) {
    int middleIndex = 0;
    
    if (!a || low > high) return -1;

    middleIndex = low + (targetValue-a[low]) / ((a[high]-a[low])/(high-low));
    if (a[middleIndex] == targetValue) return middleIndex;
    else if(a[middleIndex] < targetValue) 
        return recursiveInsertSearch(a, targetValue, middleIndex+1, high);
    else return recursiveInsertSearch(a, targetValue, low, middleIndex-1);
}

查找子数组最大和

/*
    输入一个整形数组，数组里有正数也有负数。
    数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。
    求所有子数组的和的最大值。要求时间复杂度为O(n)。
    例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5，和最大的子数组为3, 10, -4, 7, 2，
    因此输出为该子数组的和18。
*/
 int maxSumSubArray(int a[], int count) {
    int max = -1, sum = 0;
    
    if (!a || count <= 0) return -1;

    for (int i=0; i<count; i++) {
        sum += a[i];
        if (sum < 0) {
            sum = 0;
            continue;
        }
        if (max > sum) max = sum;
    }

    return max;
}