题目

前提：二分查找算法所处理的数组必须是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)