Java-データ構造とアルゴリズム-二分ルックアップ


1.二分検索の考え方:low<=highまで範囲を狭める
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