Binary Search using Bit Manipulation is quite similar to the normal binary search that we use.
Let
Let
Now let see the three cases
Let
index
point to the index in A
after i
bits from MSB are completed. When all bits are checked index
gives the position where search item may exist.
Let
j = index + 2^{i}
Now let see the three cases
- item > A[j]
hence the position ofitem
(if exists) is greater thanj
. So,index
is updated asindex + 2^{i}
, i.e. set the i^{th} bit in index - item < A[j]
the position of item is[index, j)
. So,index
is unchanged for this - item == A[j]
bingo!!
import java.util.Scanner; class Search { public static void main (String[] args) { Scanner in = new Scanner(System.in); int N = in.nextInt(); int[] A = new int[N + 1]; for (int i = 1; i <= N; i++) { A[i] = in.nextInt(); } int item = in.nextInt(); int index = 0; for (int i = Integer.highestOneBit(N); i > 0; i >>= 1) { int j = index | i; if (j <= N && item >= A[j]) { index = j; if (A[index] == item) break; } } if (item == A[index]) { System.out.println("Found at " + index); } else { if (index > 0) System.out.println("Floor is " + A[index]); if (index < N) System.out.println("Ceil is " + A[index + 1]); } } }
Input
15
2 3 5 7 11 13 17 19 23 29 31 37 43 47 53
29
Output
Found at 10