二分搜索

xiaoxiao2021-02-28  4

只要每次去掉一半的数据都可以进行二分搜索,并不总是要求有序的。 局部最小值:给定一个无序数组arr,任意两个相邻的数不想等,求任意一个局部最小的位置。

class Solution { public: int getLessIndex(vector<int> arr){ if(arr.empty()) return -1; if(arr.size()==1||arr[0]<arr[1]) return 0; if(arr[arr.size()-1]<arr[arr.size()-2]) return arr.size()-1; int low=1,high=arr.size()-2,mid; while(low<=high) { mid=low+(high-low)/2; if(arr[mid]>arr[mid-1]) high=mid-1; else if(arr[mid]>arr[mid+1]) low=mid+1; else return mid; } return -1; } };

元素最左练习题:对于一个有序数组arr,给定一个整数num,找出这个num出现的最左边的位置。

class LeftMostAppearance { public: int findPos(vector<int> arr, int n, int num){ if(!n) return -1; int low =0;high = h-1,mid; int res=-1; while(low<=high){ mid = low +(high-low)/2; if(arr[mid]<num) low=mid+1; else if(arr[mid]>num) high = mid-1; else{ res =mid; high = mid-1; } } return res; } };

循环有序数组最小值:对于一个有序循环数组arr,返回arr中的最小值。

class Minvalue{ public: int getMin(vector<int> arr,int n){ if(arr.empty()) exit(-1); if(n==1 ||arr[0]<arr[n-1]) return arr[0]; int low =0,high =n-1;mid; while(low<high){ mid =(low+high-low)/2; if(arr[low]>arr[mid]) //循环部分出现在mid 左边 high=mid; else if(arr[mid]>arr[high]) //循环部分出现在mid 右边 low = mid+1; else break; } if(low==high) return arr[low]; //特殊情况 22...1....2222 int min = arr[low]; while(low<=high){ if(arr[low]<min) min =arr[low]; low++; } return min; } };

最左原位:有一个有序数组arr,不含有重复元素,请找出arr[i]==i条件的最左位置。

class Find { public: int findPos(vector<int> arr, int n){ if(arr.empty()||arr[0]>n-1 || arr[n-1]<0) return -1; int res=-1; int low = 0,high =n-1,mid; while(low<=high){ mid = low+(high-low)/2; if(arr[mid]<mid) low = mid +1; else if(arr[mid]>mid) high = mid -1; else{ res = mid; high=mid-1; } } return res; } };

快速N次方练习题:给定K,n返回K的n次方。

class QuickPower{ public: int getPower(int k,int N){ if(k==0) return 0; if(N==0) return 1; if(k>1000000007) k=k%1000000007; vector<long> arr; vector<int> bit; long long m=N,temp=k,res; while(m){ arr.push_back(temp); temp=temp*temp; if(temp>1000000007) temp=temp%1000000007; if(m%2) bit_push_back(1); else bit.push_back(0); m=m/2; } for(int i=0,res=1;i<bit.size();i++) if(bit[i]){ res*=arr[i]; if(res>1000000007) res=res%1000000007; } return res%1000000007; } };
转载请注明原文地址: https://www.6miu.com/read-2400161.html

最新回复(0)