Java1.二分查找法 2.右移和除2的差別

1.非遞歸的二分查找和遞歸的二分查找

• 其中mid = (end - start) >>1 + start，原因是為了防止end+start溢出
• 使用位運算右移一位替代整除于2，在運算數都是正整數型的情況下不會受到影響。

//非遞歸
public static int binSearch(int srcArray[], int key) {
        int mid;
        int start = 0;
        int end = srcArray.length - 1;
        while (start <= end) {
            mid = (end - start) >>1 + start;
            if (key < srcArray[mid]) {
                end = mid - 1;
            } else if (key > srcArray[mid]) {
                start = mid + 1;
            } else {
                return mid;
            }
        }
        return -1;
    }

//遞歸
 public static int binSearch(int srcArray[], int start, int end, int key) {
        int mid = (end - start) >>1 + start;
        if (srcArray[mid] == key) {
            return mid;
        }
        if (start >= end) {
            return -1;
        } else if (key > srcArray[mid]) {
            return binSearch(srcArray, mid + 1, end, key);
        } else if (key < srcArray[mid]) {
            return binSearch(srcArray, start, mid - 1, key);
        }
        return -1;
    }
           

關于JAVA中>>1和/2的差別

結論

n為非負數時，>> 1和/ 2的結果是一樣的

n為負數且還是偶數時，>> 1和/ 2的結果是一樣的

n為負數且還是奇數時，>> 1和/ 2的結果是不一樣的

參考自關于JAVA中>>1和/2的差別（原碼反碼補碼）

原因歸納

原因是奇數除二會發生截斷現象。而>> 1和/ 2在n為負奇數時截斷的反向不一樣。

縱向比較

-5的原碼（1000 0101） 反碼（1111 1010） 補碼（1111 1011）

-5 >> 1 = (1111 1011) >> 1 = (1111 1101) = -3 （1000 0011），假設用8-bit表示一個整數，補碼表示。發現結果變小了。

-4的原碼（1000 0100） 反碼（1111 1011） 補碼（1111 1100）

-4 >> 1 = (1111 1100) >> 1 = (1111 1110) = -2 （1000 0010）

橫向比較

-5 / 2 = -2，5 / 2 = 2。這表明除二是向零取整

-5 >> 1 = -3，5 >> 1 = 2。這表明右移一位是向下取整