1 基本的二分查找
01-復(fù)雜度3 二分查找 (20分)
最開始使用的是遞歸，發(fā)現(xiàn)最后一個測試點超時了
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 10
#define NotFound 0
typedef int ElementType;
typedef int Position;
typedef struct LNode *List;
struct LNode {
ElementType Data[MAXSIZE];
Position Last; /* 保存線性表中最后一個元素的位置 */
};
List ReadInput(); /* 裁判實現(xiàn)舞丛，細(xì)節(jié)不表刁岸。元素從下標(biāo)1開始存儲 */
Position BinarySearch( List L, ElementType X );
int main()
{
List L;
ElementType X;
Position P;
L = ReadInput();
scanf("%d", &X);
P = BinarySearch( L, X );
printf("%d\n", P);
return 0;
}
/* 你的代碼將被嵌在這里 */
Position search(ElementType Data[], Position l, Position r,ElementType X){
if (l==r){
return Data[l]==X? l:NotFound;
}
Position mid = (l+r)>>1;
if (Data[mid] == X){
return mid;
} else if (Data[mid] < X){
return search(Data, mid+1, r,X);
} else {
return search(Data, l, mid-1,X);
}
}
Position BinarySearch( List L, ElementType X ){
Position p = search(L->Data, 1, L->Last,X);
return p;
}
于是改成非遞歸的形式
Position BinarySearch( List L, ElementType X ){
Position p = 0;
Position l =1,r = L->Last;
while (l<=r){
Position mid = l +((r-l)>>1);
if (L->Data[mid] == X){
p = mid;
break;
}
else if (L->Data[mid] < X){
l = mid +1;
}
else {
r = mid -1;
}
}
if (p==0){
p = NotFound;
}
return p;
}
注意：
- 上面寫的是簡單的二分查找脏里，要求數(shù)據(jù)順序存儲在數(shù)組中（如果是在鏈表中，查找的時候就不是O(1)復(fù)雜度了）虹曙，而且沒有重復(fù)數(shù)據(jù)
- 循環(huán)退出條件是
l<=r迫横，不是l<r - 取mid可以寫為
mid = l +((r-l)>>1);避免溢出，注意不要掉了兩對括號酝碳，根據(jù)優(yōu)先級（先算術(shù)運算员淫，后移位運算，最后位運算）击敌，加法優(yōu)先于右移。 - left 和 right 更新時不應(yīng)該使用mid拴事，而應(yīng)該使用mid-1或者mid+1沃斤。因為當(dāng)數(shù)組中沒有指定元素時，我們的判斷條件
while(l<=r)會導(dǎo)致程序陷入無限循環(huán)刃宵，相等才退出 - 數(shù)據(jù)量太小不適合二分查找衡瓶，比如只有10個數(shù)據(jù)元素，循環(huán)就好了
- 數(shù)據(jù)量太大牲证，比如1GB哮针，由于二分查找需要連續(xù)的內(nèi)存空間，所以也不適合
題外話：基于鏈表的二分查找其實是有的。Redis中的有序集合(sorted set)使用的“跳表（Skip List）”數(shù)據(jù)結(jié)構(gòu)十厢，就是一種基于鏈表的查找方法等太，查詢效率O(logn)， 構(gòu)建多級索引蛮放。
2 二分查找拓展
- 查找第一個值等于給定值的元素
- 查找最后一個值等于給定值的元素
- 查找第一個大于等于給定值的元素
- 查找最后一個小于等于給定值的元素
- 求一個數(shù)的算術(shù)平方根缩抡，精確到小數(shù)點后6位
- 木棒切割問題
1. 查找第一個值等于給定值的元素
如在數(shù)組{1,3,4,5,6,8,8,8,11,18}中希望查找第一個等于8的下標(biāo)位置（下標(biāo)從0開始），輸入數(shù)據(jù)格式：
10
1 3 4 5 6 8 8 8 11 18
8
運行程序后得到的結(jié)果是5
public class Solution {
/**
* @param nums: The integer array.
* @param target: Target to find.
* @return: The first position of target. Position starts from 0.
*/
public int binarySearch(int[] nums, int target) {
if (nums == null || nums.length == 0) {
return -1;
}
int start = 0;
int end = nums.length - 1;
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (nums[mid] == target) {
end = mid;
} else if (target < nums[mid]) {
end = mid;
} else {
start = mid;
}
}
if (nums[start] == target) {
return start;
}
if (nums[end] == target) {
return end;
}
return -1;
}
}
#include <stdio.h>
int a[100];
int search(int a[], int size, int X){
int left = 0, right = size-1;
while(left<=right){
int mid = left + ((right - left) >> 1);
if (X > a[mid]){
left = mid + 1;
}
else if (X < a[mid]){
right = mid -1;
}
else{ // a[mid] == X
if (mid==0 || a[mid-1] < a[mid]){
return mid;
}
else {
right = mid - 1;
}
}
}
return -1;
}
int main(){
int n = 0,x=0;
scanf("%d", &n);
for (int i=0;i<n;i++){
scanf("%d", &a[i]);
}
scanf("%d", &x);
int pos = search(a,n,x);
printf("%d", pos);
}
2. 查找最后一個值等于給定值的元素
如在數(shù)組{1,3,4,5,6,8,8,8,11,18}中希望查找最后一個等于8的下標(biāo)位置（下標(biāo)從0開始）包颁，輸入數(shù)據(jù)格式：
10
1 3 4 5 6 8 8 8 11 18
8
運行程序后得到的結(jié)果是7
public class Solution {
/**
* @param nums: An integer array sorted in ascending order
* @param target: An integer
* @return: An integer
*/
public int lastPosition(int[] nums, int target) {
if (nums == null || nums.length == 0) {
return -1;
}
int start = 0;
int end = nums.length - 1;
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (nums[mid] == target) {
start = mid;
} else if (target < nums[mid]) {
end = mid;
} else {
start = mid;
}
}
if (nums[end] == target) {
return end;
}
if (nums[start] == target) {
return start;
}
return -1;
}
}
#include <stdio.h>
int a[100];
int search(int a[], int size, int X){
int left = 0, right = size-1;
while(left<=right){
int mid = left + ((right - left) >> 1);
if (X > a[mid]){
left = mid + 1;
}
else if (X < a[mid]){
right = mid -1;
}
else{ // a[mid] == X
if (mid==size-1 || a[mid+1] > a[mid]){
return mid;
}
else {
left = mid + 1;
}
}
}
return -1;
}
int main(){
int n = 0,x=0;
scanf("%d", &n);
for (int i=0;i<n;i++){
scanf("%d", &a[i]);
}
scanf("%d", &x);
int pos = search(a,n,x);
printf("%d", pos);
}
3. 查找第一個大于等于給定值的元素
如在數(shù)組{3,4,6,7,10}中希望查找第一個大于等于5的下標(biāo)位置（下標(biāo)從0開始）瞻想，輸入數(shù)據(jù)格式：
5
3 4 6 7 10
5
運行程序后得到的結(jié)果是2
#include <stdio.h>
int a[100];
int search(int a[], int size, int X){
int left = 0, right = size-1;
while(left<=right){
int mid = left + ((right - left) >> 1);
if (a[mid]>=X){
if (mid == 0 || a[mid-1] < X){
return mid;
}
else {
right = mid - 1;
}
}
else {
left = mid +1;
}
}
return -1;
}
int main(){
int n = 0,x=0;
scanf("%d", &n);
for (int i=0;i<n;i++){
scanf("%d", &a[i]);
}
scanf("%d", &x);
int pos = search(a,n,x);
printf("%d", pos);
}
4. 查找最后一個小于等于給定值的元素
如在數(shù)組{3,4,6,7,10}中希望查找最后一個小于等于5的下標(biāo)位置（下標(biāo)從0開始），輸入數(shù)據(jù)格式：
5
3 4 6 7 10
5
運行程序后得到的結(jié)果是1
#include <stdio.h>
int a[100];
int search(int a[], int size, int X){
int left = 0, right = size-1;
while(left<=right){
int mid = left + ((right - left) >> 1);
if (a[mid] <= X){
if (mid == size-1 || a[mid+1] > X){
return mid;
}
else {
left = mid +1;
}
}
else {
right = mid - 1;
}
}
return -1;
}
int main(){
int n = 0,x=0;
scanf("%d", &n);
for (int i=0;i<n;i++){
scanf("%d", &a[i]);
}
scanf("%d", &x);
int pos = search(a,n,x);
printf("%d", pos);
}
5. 求一個數(shù)的算術(shù)平方根娩嚼，精確到小數(shù)點后6位
#include <stdio.h>
const double eps=1e-7;
double f(double x){
return x*x;
}
double mysqrt(double n){
double left = 0;
double right = n;
double mid = -1;
while (right - left > eps){
mid = (left + right)/2;
if (f(mid) > n){
right = mid;
}
else {
left = mid;
}
}
return mid;
}
int main(){
int n = 0;
scanf("%d", &n);
double root = mysqrt(n);
printf("%lf", root);
}
6. 木棒切割問題
給出N個木棒蘑险，長度已知。現(xiàn)在希望通過切割它們得到至少K個長度相等的木棒（長長度是整數(shù)）岳悟。問這些長度相等的木棒最長有多長佃迄。
例如對于3根木棒，長度分別為10竿音，24和屎，15。想要得到至少7個長度相等的木棒春瞬，那么切割的木棒最長為6柴信。
有N條繩子，它們的長度分別為Li宽气。如果從它們中切割出K條長度相同的繩子随常，這K條繩子每條最長能有多長？
#include <stdio.h>
int a[10000];
int getCurrK(int len, int n){
int currK = 0;
for (int i=0;i<n;i++){
currK += a[i]/len;
}
return currK;
}
int main(){
int n=0,k=0,left=1,right=0,len = 0,sum=0;
scanf("%d %d", &n, &k);
for (int i=0;i<n;i++){
scanf("%d", &a[i]);
sum += a[i];
}
right = sum / k;
while (left <= right){
int mid = left + ((right - left)>>1);
int currK = getCurrK(mid, n);
if (currK < k){
right = mid - 1;
} else if (currK > k){
left = mid + 1;
} else {
if (mid == sum / k || getCurrK(mid+1, n)<k ){
len = mid;
break;
} else {
left = mid + 1;
}
}
}
printf("%d", len);
return 0;
}
3 最大子列和問題
最大子列和問題的三種解法
#include <stdio.h>
// O(n^3)
int maxSubSum(int a[], int size,int max){
for (int i=0;i<size;i++){
for (int j=i;j<size;j++){
int r = 0;
for (int k=i;k<=j;k++){
r+=a[k];
}
if (r > max){
max = r;
}
}
}
return max;
}
// O(n^2)
int maxSubSum2(int a[], int size,int max){
for (int i=0;i<size;i++){
int r = 0;
for (int j=i;j<size;j++){
r+=a[j];
if (r > max){
max = r;
}
}
}
return max;
}
int conquer(int a[], int left,int mid,int right,int lr,int rr){
int maxl = 0;
int r = 0;
for(int i=mid;i>=left;i--){
r+=a[i];
if (r>maxl){
maxl = r;
}
}
int maxr = 0;
r = 0;
for (int i=mid+1;i<=right;i++){
r+=a[i];
if (r>maxr){
maxr = r;
}
}
int maxlr = maxl + maxr;
if (maxlr >= lr && maxlr >= rr){
return maxlr;
} else if (lr > maxlr && lr > rr){
return lr;
} else if (rr > maxlr && rr > lr){
return rr;
}
}
// O(NLogN) 二分法
int maxSubSum3(int a[], int left,int right){
if (left == right){
return (a[left]>0)?a[left]:0;
}
else if (left < right){
int mid = (left + right) >> 1;
int lr = maxSubSum3(a,left,mid); // 獲取左邊最大
int rr = maxSubSum3(a,mid+1,right); // 獲取右邊最大
int max = conquer(a,left,mid,right,lr,rr); // 獲取中間向兩邊擴(kuò)展的最大值萄涯，并和左邊绪氛、右邊最大比較
return max;
}
}
int main(){
int a[8] = {4,-3,5,-2,-1,2,6,-2};
int max = 0;
max = maxSubSum3(a,0,7);
printf("%d", max);
return(0);
}
當(dāng)然，最大子列和還有“在線處理”這種耗時O(N)的算法
01-復(fù)雜度2 Maximum Subsequence Sum (25分)
#include <stdio.h>
int a[100000];
int main(){
int n=0; // 讀入n個數(shù)
int max=0, thisSum = 0; // max=最終結(jié)果涝影，thisSum=當(dāng)前和
scanf("%d", &n);
for (int i=0; i<n; i++){
scanf("%d", &a[i]);
thisSum += a[i];
if (thisSum < 0 ){ // 不可能使得后面的值增大了枣察，拋棄
thisSum = 0;
}
if (thisSum >max){ // 更新當(dāng)前結(jié)果
max = thisSum;
}
}
printf("%d", max);
return 0;
}
