二分検索の注意事項とその変形

一、実現する

public int bsearch(int[] a, int n, int value) {
  int low = 0;
  int high = n - 1;

  while (low <= high) {
    int mid = (low + high) / 2;
    if (a[mid] == value) {
      return mid;
    } else if (a[mid] < value) {
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }
  return -1;
}

二、注意事項

   循環退出条件はlowです。

   lowとhighが大きいと、両者の和が溢れる可能性があります。改善方法はlow+((high-low)>>1と書くことです。

   low=mid+1、ハイ=mid-1。ここの+1と-1に注意してください。そのままlow=midまたはhigh=midと書くと、死のサイクルが発生する可能性があります。

 
三、変形
    変数1:最初の値が与えられた値に等しい要素を検索します。

public int bsearch(int[] a, int n, int value) {
  int low = 0;
  int high = n - 1;
  while (low <= high) {
    int mid = low + ((high - low) >> 1);
    if (a[mid] >= value) {
      high = mid - 1;
    } else {
      low = mid + 1;
    }
  }

  if (low < n && a[low]==value) return low;
  else return -1;
}

    変数2:最後の値が与えられた値に等しい要素を検索します。

public int bsearch(int[] a, int n, int value) {
  int low = 0;
  int high = n - 1;
  while (low <= high) {
    int mid =  low + ((high - low) >> 1);
    if (a[mid] > value) {
      high = mid - 1;
    } else if (a[mid] < value) {
      low = mid + 1;
    } else {
      if ((mid == n - 1) || (a[mid + 1] != value)) return mid;
      else low = mid + 1;
    }
  }
  return -1;
}

 
    変数3：与えられた値以上の最初の要素を検索します。

public int bsearch(int[] a, int n, int value) {
  int low = 0;
  int high = n - 1;
  while (low <= high) {
    int mid =  low + ((high - low) >> 1);
    if (a[mid] >= value) {
      if ((mid == 0) || (a[mid - 1] < value)) return mid;
      else high = mid - 1;
    } else {
      low = mid + 1;
    }
  }
  return -1;
}

    変数4：循環配列の二分割検索

def cycleBsearch(lst, b):
    if len(lst) == 0:
        return -1
    low = 0
    high = len(lst) - 1
    mid = (low + high) >> 1
    while low <= high:
        if lst[mid] == b:
            return mid
        if lst[low] <= lst[mid] <= lst[high]:
            if b < lst[mid]:
                high = mid - 1
            else:
                low = mid + 1
        if lst[low] <= lst[mid] >= lst[high]:
            if lst[low] <= b < lst[mid]:
                high = mid - 1
            else:
                low = mid + 1
        if lst[low] >= lst[mid] <= lst[high]:
            if lst[mid] < b <= lst[high]:
                low = mid + 1
            else:
                high = mid - 1
        mid = (low + high) >> 1
    return -1

 
    変数5:指定値以下の最後の要素を検索します。

public int bsearch(int[] a, int n, int value) {
  int low = 0;
  int high = n - 1;
  while (low <= high) {
    int mid =  low + ((high - low) >> 1);
    if (a[mid] > value) {
      high = mid - 1;
    } else {
      if ((mid == n - 1) || (a[mid + 1] > value)) return mid;
      else low = mid + 1;
    }
  }
  return -1;
}