【刷题笔记】--二分查找binarysearch

当给一个有序的数组，在其中查找某个数，可以考虑用二分查找。

---

题目1： 

二分查找的思路： 

设置left和right指针分别指向要查找的区间。mid指针指向这个区间的中间。比较mid指针所指的数与target。

如果mid所指的数小于target，那么就可以排除mid左边的所有数，left移向mid的右边一位，改变要查找的区间。

如果mid所指的数大于target，那么就可以排除mid右边的所有数，right移向mid的左边一位，改变要查找的区间。

代码：

int search(int* nums, int numsSize, int target){int left=0;int right=numsSize-1;int mid=(right+left)/2;while(left<=right){if(nums[mid]<target){left=mid+1;}else if(nums[mid]>target){right=mid-1;}else{return mid;}mid=(right+left)/2;}return -1;
}

---

 题目2：

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

每行的元素从左到右升序排列。
每列的元素从上到下升序排列。

示例 1：

输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
输出：true

思路： 

这个二维数组从左到右和从上到下都是有序的，这可以就可以想到用二分查找。

可以进行一行一行的二分查找即可。

代码：

bool searchMatrix(int** matrix, int matrixSize, int* matrixColSize, int target){int i;for(i=0;i<matrixSize;i++){int left=0;int right=(*matrixColSize)-1;while(left<=right){int mid=(left+right)/2;if(matrix[i][mid]<target){left=mid+1;}else if(matrix[i][mid]>target){right=mid-1;}else{return true;}}}return false;
}