题目
前提：二分查找算法所处理的数组必须是Sorted好的
给定一个数组arr和一个target value，如果target存在于arr中则返回target的index，不存在则返回-1；
arr = {1,3,4,5,6,10}, target = 6;
解题思路
二分查找又称为折半查找，仅适用于事先已经排好序的顺序表。其查找的基本思路：首先将给定值K，与表中中间位置元素的关键字比较，若相等，返回该元素的存储位置；若不等，这所需查找的元素只能在中间数据以外的前半部分或后半部分中。然后在缩小的范围中继续进行同样的查找。如此反复直到找到为止。
Code
public class Solution {
//O(n) O(1)
public int binarySearch(int[] arr, int target) {
if(arr==null||arr.length==0)return -1;
int left = 0;
int right = arr.length-1;
while(left<=right){
int mid = left+(right-left)/2;
if(arr[mid]==target){
return mid;
}
if(arr[mid]<target){
left = mid +1;
}else{
right = mid -1;
}
}
return -1;
}
}
时空复杂度
time complexity:O(lgn)
space complexity:O(1)
