順序查找

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);
}

查找子數(shù)組最大和

/*
    輸入一個(gè)整形數(shù)組，數(shù)組里有正數(shù)也有負(fù)數(shù)。
    數(shù)組中連續(xù)的一個(gè)或多個(gè)整數(shù)組成一個(gè)子數(shù)組，每個(gè)子數(shù)組都有一個(gè)和。
    求所有子數(shù)組的和的最大值。要求時(shí)間復(fù)雜度為O(n)。
    例如輸入的數(shù)組為1, -2, 3, 10, -4, 7, 2, -5，和最大的子數(shù)組為3, 10, -4, 7, 2，
    因此輸出為該子數(shù)組的和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;
}