手搓二分查找

第一种：

该种方法是若a[mid]==目标数，则让r一直等于mid，让l往右移动，一直移动到r=l，这时候跳出循环，在循环外判断
但是不能写成让l=mid，让r往左移动，比如a[2]==key，这时，mid=2,若l一直等于2，r移动到3，mid=（2+3）/2=2会一直执行while循环，跳不出来

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool binary1(int a[],int key,int len)
{	//该种方法是若a[mid]==目标数，则让r一直等于mid，让l往右移动，一直移动到r=l，这时候跳出循环，在循环外判断
//但是不能写成让l=mid，让r往左移动，比如a[2]==key，这时，mid=2,若l一直等于2，r移动到3，mid=（2+3）/2=2会一直执行while循环，跳不出来int l = 0;int r = len-1;while (l<r){int mid = l + r >>1;		//左移1位，相当于(l+r)/2if (key <= a[mid])	r = mid;else l = mid + 1;}if (a[r] == key)	return true;return	false;}int main()
{int a[7] = { 12,4,57,87,32,1,23 };sort(a, a + 7, less<int>());    //二分查找前必须先排序，且必须是升序if (binary1(a, 12, sizeof(a) / sizeof(int)))cout << "yes\n";else cout << "no\n";return 0;
}

第二种：   

该方法是在while循环中判断a[mid]是否等于key，若找到则返回true，若最后一次循环即l==r，这时a[mid]≠key，则跳出循环，返回false

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;bool binary2(int a[], int key,int len)
{	//该方法是在while循环中判断a[mid]是否等于key，若找到则返回true，若最后一次循环即l==r，这时a[mid]≠key，则跳出循环，返回falseint l = 0;int r = len - 1;while (l <= r){int mid = l + r >> 1;if (key == a[mid])	return true;else if (key > a[mid])	l = mid + 1;else r = mid - 1;}return false;
}
int main()
{int a[7] = { 12,4,57,87,32,1,23 };sort(a, a + 7, less<int>());	//二分查找前必须先排序，且必须是升序if (binary2(a, 13, sizeof(a) / sizeof(int)))cout << "yes" << endl;else cout << "no" << endl;return 0;
}