[数据结构与算法]leetcode 704. 二分查找

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

三种解法：

解法1：最基本的二分查找算法

class Solution {
 ?  public int search(int[] nums, int target) {
 ? ? ?  int left = 0;
 ? ? ?  int right = nums.length -1;
 ? ? ?  while(left<=right){
 ? ? ? ? ?  int mid = left +(right-left)/2;
 ? ? ? ? ?  if(target<nums[mid]){
 ? ? ? ? ? ? ?  right = mid-1;
 ? ? ? ? ?  }else if(target>nums[mid]){
 ? ? ? ? ? ? ?  left = mid +1;
 ? ? ? ? ?  }else if(target==nums[mid]){
 ? ? ? ? ? ? ?  return mid;
 ? ? ? ? ?  }
 ? ? ?  }
 ? ? ?  return -1;
?
 ?  }
}

解法2：寻找左侧边界的二分查找

class Solution {
 ?  public int search(int[] nums, int target) {
 ? ? ? int left = 0;
 ? ? ? int right = nums.length-1;
 ? ? ? while(left<=right){
 ? ? ? ? ? int mid = left+(right-left)/2;
 ? ? ? ? ? if(target<nums[mid]){
 ? ? ? ? ? ? ? right=mid-1;
 ? ? ? ? ? }else if(target>nums[mid]){
 ? ? ? ? ? ? ? left=mid+1;
 ? ? ? ? ? }else if(target==nums[mid]){
 ? ? ? ? ? ? ? right = mid-1;
 ? ? ? ? ? }
?
 ? ? ? }
?
// ? ?  left>=nums.length 此处要写>=;否则会出现后面的判断数组越界问题
 ? ? ?  if(left>=nums.length||nums[left]!=target){
 ? ? ? ? ?  return -1;
 ? ? ?  }
 ? ? ?  return left;
?
 ?  }
?
}

解法3：寻找右侧边界的二分查找

class Solution {
 ?  public int search(int[] nums, int target) {
 ? ? ?  int left = 0;
 ? ? ?  int right = nums.length-1;
 ? ? ?  while(left<=right){
 ? ? ? ? ?  int mid = left +(right-left)/2;
 ? ? ? ? ?  if(target<nums[mid]){
 ? ? ? ? ? ? ?  right = mid -1;
 ? ? ? ? ?  }else if(target> nums[mid]){
 ? ? ? ? ? ? ?  left = mid +1;
 ? ? ? ? ?  }else if(target == nums[mid]){
 ? ? ? ? ? ? ?  left = mid +1;
 ? ? ? ? ?  }
 ? ? ?  }
 ? ? ?  if(right<0||nums[right]!=target){
 ? ? ? ? ?  return -1;
 ? ? ?  }
 ? ? ?  return right;
 ?  }
}

• while(left<=right){}二分查找的循环体

• mid中间值定义为left+（right-left）/2的原因是防止left+right值越界

• 寻找左侧边界的二分查找；当目标值找到时，不直接返回中间值，而是锁定左侧边界，对右侧边界不断向左缩小

• 寻找右侧边界的二分查找；当目标值找到时，不直接返回中间值，而是锁定右侧边界，对右侧边界不断向右缩小

• 寻找左边界的二分查找；需要确保left值不大于数组长度，且当left值大于或等于数组长度或者下标为left的数组值不等于目标值时，返回-1；否则返回left值；右边界同理可证。