題目
前提：二分查找算法所處理的數(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)
