二分查找

1.题目描述

请实现无重复数字的升序数组的二分查找
给定一个 元素有序的（升序）整型数组 nums 和一个目标值 target  ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1
示例1
输入
复制
[-1,0,3,4,6,10,13,14],13
返回值
复制
6
说明
13 出现在nums中并且下标为 6

2.解题思路

• 简单的运用二分查找思路，左端点，右端点。
• 初始化指针left=0,right=nums.length-1.
• 当left<=right:
  • 比较nums[left]和target的大小
  • 如果nums[mid]<target，则在右侧继续搜索，left=mid+1;
  • 如果nums[mid]==target，则直接返回mid;
  • nums[mid]>target,继续在左侧搜索，right=mid-1;

3.源代码

import java.util.*;
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @param target int整型 
     * @return int整型
     */
    public int search (int[] nums, int target) {
                 int  n=nums.length;
                 int  left=0;
                 int  right=n-1;
                   while(left<=right){
                       int  mid=left+(right-left)/2;
                       if(nums[mid]<target){
                               left=mid+1; 
                       }

                       else  if(nums[mid]==target){
                               return mid;
                       }
                       else{
                              right=mid-1;
                       }    
                   }
          return -1;
    }
}

4.复杂度分析：

• 时间复杂度O(logn)
• 空间复杂度O(1)

5.提交运行情况