题目链接 

题目:

分析:

• 如果按照从头到尾的顺序一次比较, 每次只能舍弃一个元素, 效率是非常低的, 而且没有用到题目的要求, 数组是有序的
• 因为数组是有序的, 所以如果我们随便找到一个位置, 和目标元素进行比较, 如果大于目标元素, 说明该位置的右侧元素都比目标元素大, 都可以舍去, 同理, 比目标元素小可以舍去左边的元素, 具有"二段性" 
• 通过概率计算, 当我们选中间元素时, 时间复杂度最好, 引出"二分查找"算法

代码:
 

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(nums[mid] > target){right = mid - 1;}else if(nums[mid] < target){left = mid + 1;}else{return mid;}}return -1;}
}