前言

高等樹的部分結束ㄌ，我們接下來可以進入比較簡單的章節，先來看一下我們耳熟能詳的 Search，受過前面的摧殘再看這邊的 search 應該會很開心？

Linear Search

Linear Search 非常簡單，我們在這邊就說明一下他的特性即可

1. 資料可以用 Random Access(array)、Sequential Access(linklist) 的結構儲存
2. 不必事先排序

Binary Search

在進入演算法之前，我們先來說明以下的前提

1. 資料必須要已 Random Access(array) 方式儲存
2. 必須事先進行排序 (e.g. 小到大 or 大到小)

我們先思考一下，在 Sorted 的 array 中

• 如果我想找的 target 比起整條 Array 最中間的值還要大，那左半邊就可以不用找了
• 如我我想找的 target 比起整條 Array 最中間的值還要小，那右半邊就可以不用找了

依照這個觀念下去看就很好理解囉
我們分為遞迴或非遞迴兩種方式來進行演算法的撰寫

BinarySearchRec (int[] A, int k){  //target:k
    int l = 0;
    int r = A.length;
	if(r>=l){
		int mid = (l+r)/2;			
		if(a[mid] > target){
			return BinarySearchRecursive(a,target,l,mid-1);
		}
		if(a[mid] < target){
			return BinarySearchRecursive(a,target,mid+1,r);
		}
		if(a[mid] == target){
			return mid;
		}
	}
	return -1;
}

BinarySearchIter (int[] A, int k){  //target:k
	int right = arr.length-1;
	int left = 0; // last index
	while(right>=left){
		int mid = (left+right)/2; 
		if(target > arr[mid]){
			left = mid+1;
		}else if (target < arr[mid]){
			right = mid-1;
		}else{
			return mid;
		}
	}
	return -1; // means not found
}