တောင်တန်း Array တွင်အမြင့်ဆုံးအညွှန်းကိန်း


ခက်ခဲအဆင့် လွယ်ကူသော
မကြာခဏမေးတယ် Microsoft က
အခင်းအကျင်း Binary Search ကို

တောင်တန်း Array ပြinနာတွင် Peak Index ဆိုတာဘာလဲ။

Array ကို array လို့ပြောနိုင်ပါတယ် တောင်တန်း Array အောက်ပါဂုဏ်သတ္တိများကိုပြလျှင်

  1. ပေးထားသောခင်းကျင်း၏အရှည်သည် ၃ ထက်ကြီးခြင်းသို့မဟုတ်ညီမျှသင့်သည် သက်တမ်း> = 3.
  2. Array တွင်အထွတ်အထိပ်တစ်ခုသို့မဟုတ်အကြီးဆုံးဒြပ်စင်တစ်ခုသာရှိနိုင်သည်။
  3. ၎င်းကိုလိုက်နာသင့်သည် - ARRAY [0] <ARRAY [1] <ARRAY [i-1] <ARRAY [i]> ARRAY [i + 1]> ARRAY [.. ]> ARRAY [အရှည် -၁]

ကျွန်တော်တို့ရဲ့လုပ်ငန်းတာဝန်ကတောင်အမြင့်ဆုံးအညွှန်းကိန်းကိုရှာဖွေဖို့ဖြစ်တယ် အခင်းအကျင်း.

နမူနာ

input

[၅၊ ၄၊ ၃၊ ၂၊ ၁]

output

2

ရှင်းလင်းချက်

အညွှန်းကိန်း "2" ဆိုလိုသည်မှာ "30" အကြီးဆုံးတန်ဖိုးရှိပါတယ်။

တောင်တန်း Array တွင်အမြင့်ဆုံးအညွှန်းကိန်း

input

[၁၊ ၃၊ ၅၊ ၁]

output

1

ရှင်းလင်းချက်

အညွှန်းကိန်း "1" ဆိုလိုသည်မှာ "2" အကြီးဆုံးတန်ဖိုးရှိပါတယ်။

algorithm

  1. 0 မှအနိမ့်ထားပါ။
  2. ခင်းကျင်းသောအနှုတ်အနုတ် ၁ ကိုအမြင့်ထားပါ။
  3. variable တစ်ခုအလယ်မှာကြေညာပါ။
  4. အလယ်အလတ် = အနိမ့် + (မြင့်မားသော - အနိမ့်) / 2 သတ်မှတ်မည်။
  5. အနိမ့်နေစဉ် <အမြင့်ဆုံး:
    1. ခင်းကျင်း [နှစ်လယ်ပိုင်းတွင်>> = ခင်းကျင်း [အလယ်ပိုင်း + 1] ပါ။
      1. ထို့နောက်မြင့်မားသော = အလယ်အလတ်။
    2. အခြားသူ
      1. ထို့နောက်အနိမ့် = နှစ်လယ်ပိုင်း + 1 ။
  6. အနိမ့်သို့ပြန်သွားပါ။

ရှင်းလင်းချက်

ဒါကြောင့်ကျွန်တော်တို့ဟာအမြင့်ဆုံးအညွှန်းကိန်းကိုပေးထားတဲ့ခင်းကျင်းထဲမှာရှာရမယ်။ ဒီအဘို့အကျနော်တို့့ကိုသုံးပါ binary ရှာဖွေရေး အနည်းငယ်ချဉ်းကပ် ကျွန်တော်တို့ရဲ့ function array ကို getPeakIndex လို့ခေါ်ပြီး input array နှင့်အရှည်အရှည်ကိုပေးရမည်။

ကျနော်တို့ကနှစ်လယ်ပိုင်းကိုကြေညာပြီး 0 ကိုစတင်လိုက်တယ်။ အမြင့်သည် high-1 နှင့်ညီသည်၊ a ကိုဖွင့်တော့မည် နေစဉ်ကွင်းဆက် ထိုသို့မှားယွင်းသောသည်အနိမ့် <မြင့်မားသောအခြေအနေသည်အထိကြာရှည်ပါလိမ့်မယ်။ ကွင်းဆက်တစ်ခုထဲသို့ ၀ င်ပါကကျွန်ုပ်တို့သည် mid = low + (high-low) / 2 ကိုသတ်မှတ်သည်။

နမူနာ

ကျွန်ုပ်တို့၏သွင်းအားစုတန်ဖိုးများမှာ {4,8,16,32,27,9,3};

မြင့်မားတဲ့တန်ဖိုးက array အရှည် -1 => 7 - 1 = 6 ဖြစ်လိမ့်မည်

အမြင့် = 6

အနိမ့် = 0

နှစ်လယ်ပိုင်း = အနိမ့် + (မြင့်မားသောအနိမ့်) / 2 => 0 + (6 - 0) / 2 = 3

နှစ်လယ် = 3 ။

အခုဆိုရင် checwok မယ် (array [mid]> = array [mid + 1])

ဆိုလိုသည်မှာ ၃၂ သည် ၂၇ ထက်ကြီးသည် (သို့) ညီမျှသည်။ အခြေအနေသည်မှန်နေပြီးအမြင့်ဆုံးအဖြစ်သတ်မှတ်သည်

ဒီတော့အခုအနိမ့် = ၀ ။

အမြင့် = 3,

အလယ်ပိုင်း = 3;

နှစ်လယ်ပိုင်း = အနိမ့် + (မြင့်မားသောအနိမ့်) / 2 => 0 + (3 - 0) / 2 = 1

နှစ်လယ် = 1 ။

ယခုစစ်ဆေးကြည့်တော့မယ် (array [mid]> = array [mid + 1])

ဆိုလိုသည်မှာ 8 သည် 16 ထက်ကြီးသည် (သို့) ညီမျှသည်။ အခြေအနေသည်မှားယွင်းနေပြီးအခြားအစိတ်အပိုင်းတစ်ခုကိုလည်းလုပ်ဆောင်မည်ဖြစ်ပြီးအနိမ့်အမြင့် = အလယ်ပိုင်း +1;

ဒီတော့အခုအနိမ့် = ၀ ။

အမြင့် = 3,

အလယ်ပိုင်း = 1;

နှစ်လယ်ပိုင်း = အနိမ့် + (မြင့်မားသောအနိမ့်) / 2 => 2 + (3 - 2) / 2 = 2

နှစ်လယ် = 2 ။

ယခုစစ်ဆေးကြည့်တော့မယ် (array [mid]> = array [mid + 1])

ဆိုလိုသည်မှာ 16 သည် 32 ထက်ကြီးသည် (သို့) ညီမျှသည်။ အခြေအနေသည်မှားယွင်းနေပြီးအခြားအစိတ်အပိုင်းတစ်ခုကိုလည်းလုပ်ဆောင်မည်ဖြစ်ပြီးအနိမ့်အမြင့် = အလယ်ပိုင်း +1;

ဒီတော့အခုအနိမ့် = ၀ ။

အမြင့် = 3,

အလယ်ပိုင်း = 3;

ဒီမှာ loop (အနိမ့် <မြင့်) သည်လာသောအခါ၊ 3 <3 ကိုဆိုလိုသည်။ ၎င်းသည်မှားသည်

ပြီးတော့ loop ကထွက်လာပြီး low = 3 ကိုပြန်လာတယ်။

ထိုအခါ output ကိုဖြစ်လာလိမ့်မည်

အထွတ်အထိပ်အညွှန်းကိန်းဖြစ်ပါသည်: 3

C ++ တွင်အကောင်အထည်ဖော်ခြင်း

#include <iostream>
using namespace std;

int peakIndex(int arr[],int high)
{
    int low=0;
    int mid;
    high-=1;
    while( low < high )
    {
        mid = low +(high - low)/2;
        if(arr[mid]>=arr[mid+1])
        {
            high=mid;
        }
        else
        {
            low=mid+1;
        }
    }
    return low;
}
int main()
{
    int mountainArray[]= {4,8,16,32,27,9,3};
    int n = sizeof(mountainArray)/sizeof(mountainArray[0]);
    int peak=peakIndex(mountainArray,n);
    cout<<"Peak index is:"<<peak;
    return 0;
}
Peak index is:3

Java တွင်အကောင်အထည်ဖော်ခြင်း

class peakIndex {
  public static int getPeakIndex(int[] array) {
    int low = 0;
    int high = array.length - 1;
    int mid;
    while (low<high) {
      mid = low + (high - low) / 2;
      if (array[mid] >= array[mid + 1]) {
        high = mid;
      } else {
        low = mid + 1;
      }
    }
    return low;
  }

  public static void main(String[] args) {
    peakIndex pi = new peakIndex();
    int mountainArray[] = { 4, 8, 16, 32, 27, 9, 3 };
    int peak = getPeakIndex(mountainArray);
    System.out.println("Peak index is:" + peak);
  }
}
Peak index is:3

ရှုပ်ထွေးဆန်းစစ်ခြင်း

အချိန်ရှုပ်ထွေး

အို (log n) n ကခင်းကျင်း၏အရှည်ဖြစ်သည်။

အာကာသရှုပ်ထွေးမှု

အို (၁) ဘာဖြစ်လို့လဲဆိုတော့ကျွန်တော်တို့ဟာအကဲဖြတ်မှုအတွက်အပိုသို့မဟုတ်အရန်နေရာမရှိဘူး။

ကိုးကား