Java-データ構造とアルゴリズム-二分ルックアップ
4036 ワード
1.二分検索の考え方:low<=highまで範囲を狭める
2.コード:
3.結果:6
2.コード:
1 package Test;
2
3 import java.util.Arrays;
4
5 public class BinarySearch {
6
7 public static void main(String[] args) {
8 int [] a = {1,5,7,9,11,12,16,20};
9 int target = 16;
10 //System.out.println(Arrays.binarySearch(a, target));
11 System.out.println(binarySearch(a, target));
12 }
13
14 public static int binarySearch(int [] a, int target){
15 int low = 0;
16 int high = a.length - 1;
17
18 while (low <= high) {
19 int mid = (low + high) >>> 1;
20 int midVal = a[mid];
21
22 if (midVal < target)
23 low = mid + 1;
24 else if (midVal > target)
25 high = mid - 1;
26 else
27 return mid; // key found
28 }
29 return -(low + 1); // key not found.
30 }
31 }
3.結果:6