入门 对有序数组进行二分搜索 + 图解 (上篇)

1）在有序数组中确定 num 存在 还是 不存在

bool exist(int num,int arr[],int len) {if (len == 0) return false;int left = 0, right = len - 1, mid = 0;while (left <= right) {mid = left + ((right - left) >> 2);if (arr[mid] == num) return true;else if (arr[mid] > num) right = mid - 1;else left = mid + 1;}return false;
}

2）在有序数组中找 >=num 的最左位置

// 2）在有序数组中找 >= num的最左位置
int findLeft(int num,int arr[], int len) {int left = 0, right = len - 1, mid = 0;int ans = -1;while (left <= right) {mid = left + ((right - left) >> 1);if (arr[mid] >= num) {ans = mid;right = mid - 1;}else {left = mid + 1;}}return ans;
}

3）在有序数组中找 <=num 的最右位置

// 3）在有序数组中找<=num的最右位置
int findRight(int num, int arr[], int len) {int left = 0, right = len - 1, mid = 0;int ans = -1;while (left <= right) {mid = left + ((right - left) >> 1);if (arr[mid] <= num) {ans = mid;left = mid + 1;}else {right = mid - 1;}}return ans;
}

二分搜索时间复杂度O(logn) 

入门 对有序数组进行二分搜索 + 图解 (上篇)

1）在有序数组中确定 num 存在 还是 不存在

bool exist(int num,int arr[],int len) {if (len == 0) return false;int left = 0, right = len - 1, mid = 0;while (left <= right) {mid = left + ((right - left) >> 2);if (arr[mid] == num) return true;else if (arr[mid] > num) right = mid - 1;else left = mid + 1;}return false;
}

2）在有序数组中找 >=num 的最左位置

// 2）在有序数组中找 >= num的最左位置
int findLeft(int num,int arr[], int len) {int left = 0, right = len - 1, mid = 0;int ans = -1;while (left <= right) {mid = left + ((right - left) >> 1);if (arr[mid] >= num) {ans = mid;right = mid - 1;}else {left = mid + 1;}}return ans;
}

3）在有序数组中找 <=num 的最右位置

// 3）在有序数组中找<=num的最右位置
int findRight(int num, int arr[], int len) {int left = 0, right = len - 1, mid = 0;int ans = -1;while (left <= right) {mid = left + ((right - left) >> 1);if (arr[mid] <= num) {ans = mid;left = mid + 1;}else {right = mid - 1;}}return ans;
}

二分搜索时间复杂度O(logn)