Masalah dalam banyak pelaksanaan carian binari?

Kami tahu bahawa algoritma carian binari adalah lebih baik daripada algoritma carian linear. Masa yang diperlukan untuk melaksanakan algoritma ini ialah O(log n). Pada kebanyakan masa, terdapat beberapa isu dengan kod yang dilaksanakan. Mari kita pertimbangkan fungsi algoritma carian binari seperti yang ditunjukkan di bawah −

Contoh

int binarySearch(int array[], int start, int end, int key){
   if(start <= end){
      int mid = (start + end) /2); //mid location of the list
      if(array[mid] == key)
         return mid;
      if(array[mid] > key)
         return binarySearch(array, start, mid-1, key);
         return binarySearch(array, mid+1, end, key);
   }
   return -1;
}

Algoritma ini berfungsi dengan baik sehingga ia mencapai nombor yang lebih besar pada permulaan dan akhir. Jika (mula + tamat) melebihi nilai 2³² - 1, maka nombor negatif boleh dikembalikan selepas dibalut. Oleh kerana nombor negatif tidak disokong sebagai indeks tatasusunan, ini mungkin menyebabkan beberapa masalah.

Untuk menyelesaikan masalah ini, terdapat beberapa cara yang berbeza.

Kaedah 1

int mid = start + ((end - start) / 2)

Kaedah kedua hanya berfungsi di Jawa kerana tiada operator >>>

Kaedah 2 (hanya untuk Java)

int mid = (start + end) >>> 1

Memandangkan >>> tidak disokong dalam C atau C++, kita boleh menggunakan kaedah berikut.

Kaedah 3

int mid = ((unsigned int) low + (unsigned int) high) >> 1

Atas ialah kandungan terperinci Masalah dalam banyak pelaksanaan carian binari?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!