leetcode binary search
introsqrt744. Find Smallest Letter Greater Than Target (?)540. Single Element in a Sorted Array (?)
reference:
binary search
intro
//here code is in Java not C++
public int binarySearch(int[] nums, int key) {
//search for key in nums
int l = 0, h = nums.length - 1;
//<= is important
while (l <= h) {
//may have int overflow problem
int m = l + (h - l) / 2;
if (nums[m] == key) {
return m;
} else if (nums[m] > key) {
h = m - 1;
} else {
l = m + 1;
}
}
return -1;
}
时间复杂度 这种折半特性的算法时间复杂度为 O(logN)。
m 计算
有两种计算中值 m 的方式：
m = (l + h) / 2 m = l + (h - l) / 2 l + h 可能出现加法溢出，也就是说加法的结果大于整型能够表示的范围。但是 l 和 h 都为正数，因此 h - l 不会出现加法溢出问题。所以，最好使用第二种计算法方法。
sqrt
注意他是从1开始的
class Solution {
public:
int mySqrt(int x) {
if (x <= 1) {
return x;
}
int l = 1, h = x;
//again <=
while (l <= h) {
int mid = l + (h - l) / 2;
int sqrt = x / mid;
if (sqrt == mid) {
return mid;
} else if (mid > sqrt) {
h = mid - 1;
} else {
l = mid + 1;
}
}
//return h returns the lower, say sqrt(8) returns 2
return h;
}
#include <iostream>
class Solution {
public:
int mySqrt(int x) {
if (x <= 1) {
return x;
}
int l = 1, h = x;
while (l <= h) {
int mid = l + (h - l) / 2;
int sqrt = x / mid;
std::cout<<"l: "<<l<<"h: "<<h<<"mid: "<<mid<<"sqrt: "<<sqrt<<std::endl;
if (sqrt == mid) {
return mid;
} else if (mid > sqrt) {
h = mid - 1;
} else {
l = mid + 1;
}
}
std::cout<<"h: "<<h<<"before return"<<std::endl;
return h;
}
};
int main(){
int x = 8;
Solution a;
int res = a.mySqrt(x);
std::cout<<"res: "<< res<<std::endl;
return 0;
}
744. Find Smallest Letter Greater Than Target (?)
class Solution {
public:
char nextGreatestLetter(vector<char>& letters, char target) {
int l=0, h=letters.size() - 1;
while(l <= h){
int mid = l + (h-l)/2;
if(letters[mid]<=target){
l = mid + 1;
}
else{
h = mid - 1;
}
}
return l<letters.size() ? letters[l]:letters[0];
}
};
540. Single Element in a Sorted Array (?)
class Solution {
public:
int singleNonDuplicate(vector<int>& nums) {
//注意要size - 1
int l=0, h=nums.size()-1;
while(l<h){
int m=l+(h-l)/2;
//% 取余数
if (m % 2 == 1) {
m--; // 保证 l/h/m 都在偶数位，使得查找区间大小一直都是奇数
}
if(nums[m] == nums[m + 1]){
l = m+2;//如果领着的两个相等，要找的[m+2,h]
}
else{
h=m; //如果两个不等，[l,m]
}
}
return nums[l];
}
};
class Solution {
public:
int firstBadVersion(int n) {
int l=1, h=n;
while(l<h){
int m = l+(h-l)/2;
if(isBadVersion(m)){
h = m;//[l,m]
}
else{
l = m+1;//[m+1,h]
}
}
return l;
}
};
