Binary Search using Bit Manipulation

Binary Search using Bit Manipulation is quite similar to the normal binary search that we use.
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 + 2i
Now let see the three cases

1. item > A[j]
   hence the position of item (if exists) is greater than j. So, index is updated as index + 2i, i.e. set the i^th bit in index
2. item < A[j]
   the position of item is [index, j). So, index is unchanged for this
3. 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