題目

前提：二分查找算法所處理的數(shù)組必須是Sorted好的
給定一個(gè)數(shù)組arr和一個(gè)target value，如果target存在于arr中則返回target的index，不存在則返回-1；
arr = {1,3,4,5,6,10}, target = 6;

解題思路

二分查找又稱為折半查找，僅適用于事先已經(jīng)排好序的順序表。其查找的基本思路：首先將給定值K，與表中中間位置元素的關(guān)鍵字比較，若相等，返回該元素的存儲(chǔ)位置；若不等，這所需查找的元素只能在中間數(shù)據(jù)以外的前半部分或后半部分中。然后在縮小的范圍中繼續(xù)進(jìn)行同樣的查找。如此反復(fù)直到找到為止。

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;
  }
  
}

時(shí)空復(fù)雜度

time complexity:O(lgn)
space complexity:O(1)