1. 二分法
二分查找也属于顺序表查找范围，二分查找也叫做折半查找，二分查找的时间效率为(logN)
二分查找的基本思想是：在有序表中，取中间记录作为比较对象，若给定值与中间记录的关键字相等，则查找成功，如果给定值小于中间值，则查找数组的前半段，否则查找数组的后半段。
二分查找只适用于有序数组或者链表
二分法常见题目汇总
一、剑指offer
二、leecode
- 题目描述：
- 问题分析，由于每一行从左到右递增，每一列从上到下递增，因此我们可以考虑左下角元素，从左到右递增，从下到上递减
若需要查找的元素target等于左下角元素，则查找到，若target小于左下角元素，向上移动，若target大于左下角元素，则向右移动
- 代码参考
1 class Solution {
2 public:
3 bool Find(int target, vector<vector<int> > array) {
4 if(array.empty())
5 return 0;
6 int rows=array.size()-1;
7 int cols=0;
8 while(rows>=0&&cols<array[0].size())
9 {
10 if(target>array[rows][cols])
11 ++cols;
12 else if(target<array[rows][cols])
13 --rows;
14 else
15 return true;
16 }
17 return false;
18 }
19 };
- 题目描述
- 问题分析
首先要搞定出旋转数组的定义，其是将一个非递减排序的数组的一个旋转，因此，旋转数组是由两个递增的子数组组成，并且第一个子数组中的元素都比第二个子数组中元素大。因此，旋转数组的最小数字一定是第二个递增子数组的头元素。因此寻找旋转数组的最小数字的方法如下：
首先设置三个指针，first指向数组头，mid指向数组中间，last指向数组尾
如果mid>first,则mid在第一个递增的子数组中，最小值在数组的后半部分
如果mid<last，则mid在第二个递增的子数组中，最小值在数组的前半部分
- 参考代码
1 class Solution {
2 public:
3 int minNumberInRotateArray(vector<int> rotateArray) {
4 int first=0;
5 int last=rotateArray.size()-1;
6 int mid=first;
7 while(rotateArray[first]>=rotateArray[last])
8 {
9 if(last-first==1)
10 {
11 mid=last;
12 break;
13 }
14 else
15 {
16 int mid=(first+last)/2;
17 if(rotateArray[first]<=rotateArray[mid])
18 first=mid;
19 else if(rotateArray[last]>=rotateArray[mid])
20 last=mid;
21 }
22 }
23 return rotateArray[mid];
24 }
25 };
- 题目描述
- 问题分析
为了统计数字在排序数组中出现的次数，我们可利用二分法，找到第一个出现的k，再找到最后一个出现的k，即可以实现统计数字在排序数组中出现的次数
为了找到第一次出现的k，三个指针，一个指针指向数组头，一个指针指向数组尾，一个指针指向中间。如果中间指针指向的数字等于要查找的k，则判断中间指针的前一个数字是否是k,如果不是k，则找到第一个出现的k，如果是k，则第一个出现的k 在数组的前半部分。如果中间指针指向的数字小于k，则k在数组的后半部分，如果中间指针指向的数字大于k，则k在数组的前半部分
为了找到最后一次出现的k，方法是类似的，不同之处在于，如果中间指针等于k，则判断中间指针的后一个数字是否为k，如果不是k，则找到最后一个k出现的位置，否则，最后一个k出现的位置在数组的后半部分
- 参考代码
1 class Solution {
2 public:
3 //找到第一个出现的k，如果mid==k,则判断mid-1是否为k，如果为k，则第一个出现的k在数组的前半部分
4 //如果不为k，则找到第一个出现的K的位置
5 //如果mid<k，则k在数组的后半部分
6 //如果mid>k，则k在数组的前半部分
7 int getFirstk(vector<int>&data,int k,int begin,int end)
8 {
9 int mid=(begin+end)/2;
10 if(begin>end)
11 return -1;
12 else
13 {
14 mid=(begin+end)/2;
15 if(data[mid]==k)
16 {
17 if(mid==0||(mid>0&&data[mid-1]!=k))
18 return mid;
19 else
20 end=mid-1;
21 }
22 else if(data[mid]>k)
23 end=mid-1;
24 else
25 begin=mid+1;
26 return getFirstk(data,k,begin,end);
27 }
28 }
29 //找到最后一个k出现的位置
30 int getLastk(vector<int>&data,int k,int begin,int end)
31 {
32 int mid;
33 int len=data.size();
34 if(begin>end)
35 return -1;
36 else
37 {
38 mid=(begin+end)/2;
39 if(data[mid]==k)
40 {
41 if((data[mid+1]!=k&&mid<len-1)||mid==len-1)
42 return mid;
43 else
44 begin=mid+1;
45 }
46 else if(data[mid]>k)
47 end=mid-1;
48 else
49 begin=mid+1;
50 return getLastk(data,k,begin,end);
51 }
52 }
53 int GetNumberOfK(vector<int> data ,int k) {
54 if(data.empty())
55 return 0;
56 int first=0;
57 int last=data.size()-1;
58 int firstk=getFirstk(data,k,first,last);
59 int lastk=getLastk(data,k,first,last);
60 int number=0;
61 if(firstk>-1&&lastk>-1)
62 number=lastk-firstk+1;
63 return number;
64 }
65 };
二、leecode刷题
- 题目描述
- 问题分析
这道题和前面二维数组的查找是有类似的地方的，二维矩阵从左到右非递增，从上到下非递增，对于左下角元素，从左到右递减，从下到上递增，从左下角元素开始进行扫描，如果当前元素为正，则当前元素以上的元素都比其大，因此都为正，因此向右查找；如果当前元素为负，则从当前元素开始的每一个元素都为负，统计负数的个数并且向上一排寻找
- 代码参考
1 class Solution {
2 public:
3 int countNegatives(vector<vector<int>>& grid) {
4 if(grid.empty())
5 return 0;
6 int row=grid.size()-1;
7 int col=0;
8 int number=0;
9 int rows=grid.size();
10 int cols=grid[0].size();
11 while(row>=0&&col<grid[0].size())
12 {
13 if(grid[row][col]>=0)
14 {
15 ++col;
16 continue;
17 }
18 else
19 {
20 number+=cols-col;
21 --row;
22 }
23
24 }
25 return number;
26 }
27 };
- 题目描述
- 题目分析
要寻找比目标字母大的最小字母，采用二分法。
1. 对下标作二分，找到第一个大于target值的下标
2. target可能比letters中的所有元素都小，也可能比letters中的所有元素都大，因此第一个大于target值的下标取值范围为[0,letters.size()]
3. 当left==right时退出，因此循环条件为while(left<right)
4. 当letters[mid]>target，mid可能是结果，因此在数组的前半部分寻找
5. 当letters[mid]<=target，mid不可能是结果，直接舍弃，因此在数组的后半部分寻找
6. 当循环退出时,left==right，若target大于letters中的所有元素，left=letters.size()，此时返回letters[0]
- 参考代码
1 class Solution {
2 public:
3 char nextGreatestLetter(vector<char>& letters, char target) {
4 int left=0;
5 int right=letters.size();
6 while(left<right)
7 {
8 int mid=(left+right)/2;
9 //如果letters[mid]>target，mid是可能结果，在数组的前半部分
10 if(letters[mid]>target)
11 right=mid;
12 //如果letters[mid]<=target，mid不可能是结果，舍去，在数组后半部分
13 else
14 left=mid+1;
15 }
16 //如果target大于数组中的所有元素时，left==letters.size(),返回letters[0]
17 if(left==letters.size())
18 return letters[0];
19 else
20 return letters[left];
21 }
22 };
2. 双指针法