一、适用条件
二分查找适用条件为：
- 数组问题
- 有序且无重复元素的数组
如【LeetCode 704】：给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
二、方法类型
二分查找法的思路主要是根据区间定义的“不变量”进行划分的。二分法中区间的定义主要有两种：
- 左闭右闭[left,right]
意思是target值在区间[left,right]中,那么left与right的关系是 “<=”
while(left<=right){ xxxx; }
- 左闭右开[left,right）
意思是target值在区间[left,right）中，那么left与right的关系是“<”
while(left<right){ xxx; }
三、二分法的两种写法
根据例题：
3.1第一种写法“左闭右闭”
int search(int* nums, int numsSize, int target){ //step1:写出临界条件变量：left,right int left=0; int right=numSize-1; //------------------------ //step2：写出区间--左闭右闭;写出middle动态值 while(left<=right){ int middle=left+((right-left)/2);//数组取中间值赋给middle变量 //step3:根据条件移动middle值 if(nums[middle]>target){ //step4:往条件里补充条件(left,right指针如何动态移动？) right=middle-1; }else if(nums[middle<target]){ left=middle+1 }else{ return middle;//找到目标值target=middle } } return -1; }
3.2第二种写法“左闭右开”
int search(int* nums, int numsSize, int target){ //step1:写出临界条件变量：left,right int left=0; int right=numSize-1; //------------------------ //step2：写出区间--左闭右闭;写出middle动态值 while(left<right){ int middle=left+((right-left)/2);//数组取中间值赋给middle变量 //step3:根据条件移动middle值 if(nums[middle]>target){ //step4:往条件里补充条件(left,right指针如何动态移动？) right=middle; }else if(nums[middle<target]){ left=middle+1 }else{ return middle;//找到目标值target=middle } } return -1; }
return middle;//找到目标值target=middle } } return -1;
}
文
