二分查找的概念

二分查找也称为折半查找。

• 查找要求
  要求为线性表且采用顺序存储结构，而且表中的元素按关键字有序排序。
• 查找过程
  从表的中间记录开始，如果给定的值和中间的记录的关键字相等，则查找成功；如果给定的值大于或小于中间记录的关键字，则在表中大于或小于中间记录的那一半查找，这样重复的操作，直到查找成功，或者在某一步中查找区间为空，则代表查找失败。
  为了标记查找过程中每一位的查找区间，下面分别用low和high来表示当前查找的下届和上界，mid为区间的中间位置。
• 查找步骤

1. 置查找区间初值，low=1，high=表长
2. 当low小于等于high时，循环以下操作

• mid取值为low和high的中间值；
• 将给定值于中间位置记录的关键字进行比较，若相等则查找成功，返回中间位置mid；
• 若不相等则利用中间位置记录将表对分成前后两个子表。如果给定值比中间位置记录的关键字小，则high取为mid-1；否则low取为mid+1；

3. 循环结束，说明查找区间为空，则查找失败。返回-1；

• Java代码

public int search(int[] nums, int target) {     int low=0,high=nums.length-1,mid=0;     while(low<=high){  mid=(high+low)/2;  if(target==nums[mid]) return mid;  else if(target<nums[mid]) high=mid-1;  else low=mid+1;     }     return -1;}

好看字体下载