二分查找属于静态查找表,当以有序表表示静态查找表时,查找函数可用折半查找来实现。
查找过程:先确定待查记录所在的范围(区间),然后逐步缩小范围直到找到或找不到该记录为止。
以处于区间中间位置记录的关键字和给定值比较,若相等,则查找成功,若不等,则缩小范围,直至新的区间中间位置记录的关键字等于给定值或者查找区间的大小小于0时(表明查找不成功)为止。
[1,1]左闭右闭时包含一个元素1,则中间值-1;
[1,1)左闭右开时不包含元素1,则中间值不用-1;
注意数组下标值和数组值;
此处以LeetCode 704题为例:
class Solution {
public int search(int[] nums, int target) {
int left=0;
int right=nums.length-1;
while(left<=right){
int middle=(right-left)/2+left;
int mid=nums[middle];
if(mid>target){
right=middle-1;
}else if(nums[middle]<target){
left=middle+1;
}else if(nums[middle]==target){
return middle;
}
}
return -1;
}
}