二分查找

1.算法思想

二分查找(折半查找)：有序数组(升序或降序，可以不连续)，每次缩小一半的区间。
时间复杂度：O(log n)
空间复杂度：循环实现是 O(1)，递归实现是 O(log n)

2.代码实现

C语言求数组长度：

int n = sizeof(A)/sizeof(A[0]);

(1)循环实现

1.C语言实现

//binarySearch.c : 二分查找(折半查找):要求数组必须是有序的(升序或降序，可以不连续)
#include <stdio.h>int binarySearch(int A[], int n, int key)
{int left = 0, right = n-1;while(left <= right){int mid = left + (right-left)/2;if(key < A[mid]){        //目标key在左半区间right = mid-1;}else if(key > A[mid]){  //目标key在右半区间left = mid+1;}else{                   //key == midreturn mid;}}return -1;
}int main()
{int A[] = {01,20,27,59,71,3702,10247};  int n = sizeof(A)/sizeof(A[0]);int pos = binarySearch(A,n,10247);printf("pos = %d\n", pos);return 0;
}

2.C++实现

#include <iostream>
#include <vector>
using std::cout;
using std::vector;int binarySearch(const vector<int>& arr, int target)
{int left = 0, right = arr.size()-1;while(left <= right){//mid的声明要放在循环里面int mid = left + (right-left)/2;  //避免整数溢出if(target < arr[mid]){       //目标在左半区间right = mid -1;}else if(target > arr[mid]){ //目标在右半区间left = mid + 1;}else{return mid;}}return -1;
}int main()
{//二分查找要求是有序数组vector<int> arr = {1,3,5,7,9,11,13,15,17,19,21,23};int target = 21;int pos = binarySearch(arr, target);if(pos == -1){cout << "未找到目标值" << target << "\n";}else{cout << "目标值" << target << "的下标为" << pos << "\n";}return 0;
}

(2)递归实现

//二分查找(折半查找):要求数组必须是有序的(升序或降序，可以不连续)#include <stdio.h>//1.循环实现
int binarySearchIterative(int A[], int n, int key)
{int left = 0, right = n-1;while(left <= right){int mid = left + (right-left)/2;if(key < A[mid]){        //目标key在左半区间right = mid-1;}else if(key > A[mid]){  //目标key在右半区间left = mid+1;}else{                   //key == midreturn mid;}}return -1;
}//2.递归实现
int binarySearchRecursive(int A[], int left, int right, int key)
{//递归出口if(left > right)    return -1;//递归公式int mid = left + (right-left)/2;if(key < A[mid]){        //目标在左半区间return binarySearchRecursive(A, left, mid-1, key);}else if(key > A[mid]){  //目标值在右半区间return binarySearchRecursive(A, mid+1, right, key);}else{                   //目标值 == A[mid]return mid;}
}int main()
{int A[] = {1,20,27,59,71,88,100,3702,10247};  int n = sizeof(A)/sizeof(A[0]);while(1){int key;printf("请输入要查找的数字: ");scanf("%d",&key);int posI = binarySearchIterative(A,n,key);int posR = binarySearchRecursive(A,0,n-1,key);printf("posI = %d\n", posI);printf("posR = %d\n", posR);}return 0;
}

3.题目练习

1.力扣704：二分查找
https://leetcode.cn/problems/binary-search/

参考答案：C语言实现

//二分查找的循环实现
int search(int* nums, int numsSize, int target) {int left = 0, right = numsSize-1;while(left <= right){int mid = left + (right-left)/2;if(target < nums[mid]){        //目标在左半区间right = mid-1;}else if(target > nums[mid]){  //目标在右半区间left = mid+1;}else{                         //target == nums[mid]return mid;}}return -1;
}