.jpeg)
一直切一半的找法。
常見於二元樹，排序後比大小問題。
背景知識
雙指針
搜尋前須先排序完成
理解問題
二元搜尋排序後列表
思路視覺化
1
2
3
4
5
| left, right = 0, 4
[ 2, 3, 4, 10, 40 ], find 3
mid ==2, 0, 1
nums[mid] == 4, 2, 3
|
Java
TC: O(nlogn): log base is 2, half each time
SC: O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| import java.util.*;
class BinarySearch {
private static int search(int [] nums, int target){
int left = 0, right = (nums.length -1), count = 1, mid;
while(left <= right){
mid = (left + right) / 2;
System.out.println("run "+ count + " times");
count +=1;
System.out.println(mid+" "+nums[mid]);
if(nums[mid] == target){
System.out.println("found: "+ nums[mid]);
return mid;
}
if(nums[mid] < target){ // target in right part
left = mid + 1;
}else{// target in left part
right = mid - 1;
}
}
return -1;
}
public static void main(String[] args) {
int [] nums = { 2, 3, 4, 10, 40 };
System.out.println(search(nums , 3));
}
}
>
java -cp /tmp/fqlpjpJwBO BinarySearch
run 1 times
2 4
run 2 times
0 2
run 3 times
1 3
found: 3
1
|
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| def search(nums, target):
left, right = 0, len(nums) -1
count = 1
while left <= right:
mid = (left + right)//2
print("run "+str(count)+" times")
count += 1
print(mid, nums[mid])
if nums[mid] == target:
return "found: "+ str(nums[mid])
if nums[mid] <target:
left = mid +1
else:
right = mid -1
return -1
print(search([ 2, 3, 4, 10, 40 ], 3))
>
run 1 times
2 4
run 2 times
0 2
run 3 times
1 3
found: 3
|